3. Longest Substring Without Repeating Characters

Problem Link

Description

---

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

 

Example 1:

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

Example 2:

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

Example 3:

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.

Solution

---

Python3

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        N = len(s)
        count = Counter()
        res = 0
        i = 0
 
        for j, x in enumerate(s):
            count[x] += 1
 
            while count[x] > 1:
                count[s[i]] -= 1
                i += 1
            
            res = max(res, j - i + 1)
 
        return res

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0, N = s.size();
        unordered_map<int, int> count;
 
        for (int i = 0, j = 0; j < N; j++) {
            count[s[j]]++;
 
            while (count[s[j]] > 1) {
                count[s[i]]--;
                i++;
            }
 
            res = max(res, j - i + 1);
        }
 
        return res;
    }
};