Sliding window

Why it costs this much

The right edge moves forward n times and the left edge never moves backward, so each element enters and leaves the window at most once.

Code

def longest_unique(s):
    last, left, best = {}, 0, 0
    for right, ch in enumerate(s):          # right moves n times
        if ch in last and last[ch] >= left:
            left = last[ch] + 1             # left only moves forward
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Common pitfalls

It works when shrinking the window cannot break the constraint, such as sums of positive numbers. With negative numbers, use prefix sums and a hash map instead.

Operation by operation

Two pointers and sliding window. Each pointer moves in one direction only and never backs up, so together they make at most 2n moves. A window that tracks counts needs O(k) space for k distinct values.