Longest Substring w/o Repeats

Grow a window to the right; when a character repeats inside it, jump the left edge past the previous occurrence. Every index is visited at most twice.

Category: Sliding Window
Time complexity: O(n)
Space complexity: O(k)

Pseudocode

expand right pointer
if char seen inside window
  move left past its last index
track the longest window

Reference implementation

lo = 0; seen = {}
for hi, ch in enumerate(s):
    if ch in seen and seen[ch] &gt;= lo:
        lo = seen[ch] + 1
    seen[ch] = hi
    best = max(best, hi - lo + 1)

Open the interactive Longest Substring w/o Repeats visualisation →