3. Longest Substring Without Repeating Characters

Posted on Edited on In

3. Longest Substring Without Repeating Characters

Description

Difficulty: Medium

Related Topics: Hash Table, String, Sliding Window

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

1
2
3
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int count[256]{};
        int res = 0, left = 0, right = 0;
        while (right < s.size()) {
            int c = s[right++];
            count[c]++;
            while (count[c] > 1) {
                // We should decrement d here no matter if d
                // is the same as c
                int d = s[left++];
                count[d]--;
            }
            res = max(res, right - left);
        }
        return res;
    }
};