Optimal Sliding Window with Hash Map:
- Expand a window with a right pointer while using a hash map of last seen indices to jump the left pointer past duplicates.
def length_of_longest_substring(s: str) -> int:
char_index_map = {}
max_length = 0
left = 0
for right, char in enumerate(s):
if char in char_index_map and char_index_map[char] >= left:
left = char_index_map[char] + 1
char_index_map[char] = right
max_length = max(max_length, right - left + 1)
return max_length
Complexity & Key Logic:
- Time Complexity: O(N) single-pass traversal of string length N.
- Space Complexity: O(min(N, M)), where M is alphabet size (at most 128 for ASCII or 26 for lowercase).
- Algorithm Details:
- Track the last seen index of each character.
- If char was seen at or after left, duplicate detected: jump left to char_index_map[char] + 1.
- Update character's newest index and calculate max_length = max(max_length, right - left + 1).