leetcode-3

3. Longest Substring Without Repeating Characters

Leetcode 3

I solved this problem using C++.
My idea: use unordered_set to store the characters in the substring and use two pointers to iterate through the string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution
{
public:
    int lengthOfLongestSubstring(string s) {
        int lt = 0, rt = 0, maxLength = 0;
        unordered_set<char> charSet;
        while (rt < s.size()) {
            char ch = s[rt];
            if (charSet.find(ch) == charSet.end()) {
                // not in set
                charSet.insert(ch);
                rt++;
            } else {
                maxLength = max(maxLength, rt - lt); // update maxLength
                // jump to the same character from the left side
                for (int i = lt; i < rt; i++) {
                    if (s[i] == ch) {
                        lt = i + 1;
                        break;
                    } else {
                        charSet.erase(s[i]);
                    }
                }
                charSet.insert(ch);
                rt++;
            }
        }
        return max(maxLength, rt - lt); // return the last length
    }
};

e.g.

input: s = “pwwkew”
output: 3

  1. lt = 0, rt = 0, maxLength = 0, charSet = {}
  2. charSet.insert(‘p’), rt = 1
  3. charSet.insert(‘w’), rt = 2
  4. s[rt] = ‘w’, charSet.find(‘w’) != charSet.end()
    4.1. maxLength = max(0, 2 - 0) = 2
    4.2. search for ‘w’ in the set, if not found, erase the character from the set
    4.3. i = 0, s[i] = ‘p’, charSet.erase(‘p’)
    4.4. i = 1, s[i] = ‘w’, lt = i + 1 = 2
    4.5. charSet.insert(s[rt]), and rt++, now charSet = {‘w’} and ‘p’ is erased
  5. charSet.insert(‘k’), rt = 3
  6. charSet.insert(‘e’), rt = 4
  7. charSet.insert(‘w’), rt = 5
  8. s[rt] = ‘w’, charSet.find(‘w’) != charSet.end()
    8.1. maxLength = max(2, 5 - 2) = 3
    8.2. search for ‘w’ in the set, if not found, erase the character from the set
    8.3. i = 2, s[i] = ‘w’, lt = i + 1 = 3
    8.4. charSet.insert(s[rt]), and rt++, now charSet = {‘k’, ‘e’} and ‘w’ is erased
  9. now rt = 6 and rt < s.size() is false, return max(3, 6 - 3) = 3

conclusion

I remembered this problem when I was grade 1 in college, and I found it difficult to solve at that time.
Now I can solve it quickly…😏😋