Optimal▶ Animated
Grow right one step at a time; on a repeat, jump left past the previous occurrence.
Maintain last[ch] = most recent index of each character. When s[right] was last seen inside the current window, move left to just after that position. Then record the new index and measure the window.
Algorithm
last = {},left = 0,best = 0.- For each
right: ifs[right]inlastandlast[s[right]] >= left, setleft = last[s[right]] + 1. last[s[right]] = right;best = max(best, right − left + 1).- Return
best.
- Time
- O(n)
- Space
- O(min(n, alphabet))
Each character is processed once; the map holds at most one entry per distinct character.
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: last: dict[str, int] = {} # char -> most recent index left = 0 # window is s[left..right] best = 0 for right, ch in enumerate(s): if ch in last and last[ch] >= left: left = last[ch] + 1 # jump past the previous occurrence last[ch] = right best = max(best, right - left + 1) return best