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

  • Sliding window

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) {
        unordered_map<char, int> window;
        int res = 0, left = 0, right = 0;
        while (right < s.size()) {
            char c = s[right++];
            window[c]++;
            while (window[c] > 1) {
                // We should decrement d here no matter if d
                // is the same as c
                char d = s[left++];
                window[d]--;
            }
            res = max(res, right - left);
        }
        return res;
    }
};