Q24: Longest Substring Without Repeating Characters. - DSA Patterns (Multi-Lang)

In Simple Words: Sliding window with right pointer expanding. Store last seen index of each character. If character was seen within current window, jump left pointer to lastSeen[c] + 1.

Time: $O(N)$ | Space: $O(\min(N, \Sigma))$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def lengthOfLongestSubstring(s: str) -> int:
    last_seen = {}
    l = 0
    max_len = 0
    for r, c in enumerate(s):
        if c in last_seen and last_seen[c] >= l:
            l = last_seen[c] + 1
        last_seen[c] = r
        max_len = max(max_len, r - l + 1)
    return max_len