Know this before you start: “Track counts inside the window with a map or set”

Tracking what's inside a window

Keep a hash map (or set) of what's in the window, updated as items enter and leave, so checking the window's rule is O(1).

The idea

A window's rule is usually about its contents: no letter twice, at most k distinct values, contains all of these letters. Recounting the window every step would be slow.

Instead keep counts for the window in a map: +1 when an item enters, −1 when it leaves (delete it at 0 so len(map) is the number of distinct items).

See it step by step

Longest stretch with at most 2 distinct letters in “eceba”

e → {e:1}; c → {e:1, c:1}; e → {e:2, c:1}: length 3
b → 3 distinct: drop from the left: e → {e:1, c:1, b:1}, c → {e:1, b:1}
a → too many again, shrink. Best stays 3 (“ece”).

In code (Python)

def longest_two_distinct(s):
    counts = {}
    left = best = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        while len(counts) > 2:
            out = s[left]
            counts[out] -= 1
            if counts[out] == 0:
                del counts[out]        # so len() counts distinct letters
            left += 1
        best = max(best, right - left + 1)
    return best

print(longest_two_distinct("eceba"))   # 3

O(n) time, O(k) space for k distinct items in the window.

When you'll use it

Anagram / permutation in a string, minimum window containing letters, at most k distinct, character replacement.

Common mistakes

Leaving zero counts in the map, so “number of distinct” is wrong.
Updating the map for the leaving item before moving left (or after the wrong index).