Longest Substring Without Repeating Characters
Description
Given a string s, find the length of the longest substring without duplicate 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. Note that "pwke" is a subsequence, not a substring.
Constraints
0 <= s.length <= 5 * 10^4s consists of English letters, digits, symbols and spaces
Complexity
Show Complexity
- Time:
O(n) - Space:
O(min(m, n))
Hints
Show Hints
- Pattern
- Sliding window with hash set/map
- Approach
- Maintain a sliding window [left, right]. When a duplicate is found, move left pointer past the previous occurrence of that character.
- Complexity
- Use a set to track characters in current window, expand right, shrink left on duplicate
Solutions
Show PY Solution
def solution(s: str) -> int:
m = {}
count = 0
left = 0
for right in range(len(s)):
c = s[right]
while c in m and m[c] >= left:
left = m[c] + 1
m[c] = right
count = max(count, right - left + 1)
return count