Longest Substring Without Repeating Characters
Given a string `s`, find the length of the longest substring that contains no duplicate characters. **Core Insight:** Sliding window with a hash set. Maintain a window `[left, right]` that always contains only unique characters. Expand `right` one character at a time. If the new character is already in the window, shrink from the left (advancing `left` and removing characters from the set) until the duplicate is gone. Track the maximum window size seen. **Algorithm:** Initialize `left = 0`, an empty set `seen`, and `maxLen = 0`. For each `right` from 0 to n-1: while `s[right]` is in `seen`, remove `s[left]` from the set and increment `left`. Add `s[right]` to `seen`. Update `maxLen = max(maxLen, right - left + 1)`. **Optimisation:** Use a hash map storing the last seen index of each character. When a duplicate is found, jump `left` directly to `lastSeen[char] + 1` instead of shrinking one step at a time. **Complexity:** Time O(n) — each character is added and removed from the set at most once. Space O(min(n, alphabet_size)).
Constraints
- •
0 ≤ s.length ≤ 5 × 10⁴
def lengthOfLongestSubstring(s: str) -> int:
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len