Windows with a hash map

Many window questions are about the contents of the window, not its sum: no repeated characters, at most k distinct values, contains every letter of a pattern. A hash map (dictionary) from value to count, or value to last index, describes those contents.

When an element enters, increment its count; when it leaves, decrement it (and delete it at zero if you track the number of distinct keys with len(map)). Combined with the grow-and-shrink loop of a variable window, this solves classic problems such as Longest Substring Without Repeating Characters and Minimum Window Substring in O(n).

1. 1Decide what the map stores: counts of each value in the window, how many of each character you still need, or the last index where each character was seen.
2. 2Grow: add s[right] and update its entry in O(1).
3. 3Keep a single number that tells you if the window is valid, for example 'number of distinct keys', 'characters still missing' or 'does the new character already appear'. Update it only when a count crosses an important boundary (0 to 1, 1 to 0).
4. 4Shrink: while the window is invalid (for longest problems) or valid (for shortest problems), remove s[left], update its count and the summary number, then move left.
5. 5Shortcut for 'no repeats': store last seen index; when s[right] was seen inside the window, jump left directly to last index + 1. For 'abcabcbb' this gives 3 ('abc').

from collections import Counter

def longest_unique(s):
    last = {}                        # char -> last index seen
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1      # jump past the earlier copy
        last[ch] = right
        best = max(best, right - left + 1)
    return best


def min_window(s, t):
    need = Counter(t)                # how many of each char we still owe
    missing = len(t)                 # total chars still owed
    left, best = 0, (0, float("inf"))
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:          # window covers t: shrink it
            if right - left < best[1] - best[0]:
                best = (left, right)
            need[s[left]] += 1
            if need[s[left]] > 0:    # we just gave up a needed char
                missing += 1
            left += 1
    return "" if best[1] == float("inf") else s[best[0]:best[1] + 1]

longest_unique uses a last-index map and jumps left directly: O(n) time, O(alphabet) space. min_window uses a need map and a single missing counter, so validity is checked in O(1) instead of comparing whole maps: O(len(s) + len(t)) time.

Cost: Time O(n), each element enters and leaves once, with O(1) average hash map operations. Space O(k) where k is the number of distinct values in the window (at most the alphabet size).