Two Pointer Expansion — Grow a Valid Window

Expansion often grows a window until a condition breaks, then contracts from the other side (see sliding window lesson too).

Try this in Python

def max_len_substring_k_distinct(s: str, k: int) -> int:
    from collections import Counter

    left = 0
    best = 0
    cnt = Counter()
    for right, ch in enumerate(s):
        cnt[ch] += 1
        while len(cnt) > k:
            cnt[s[left]] -= 1
            if cnt[s[left]] == 0:
                del cnt[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best


print(max_len_substring_k_distinct("eceba", 2))

Key takeaways

• Expand right, shrink left while invalid.
• Frequency map is common.
• Invariant: window always valid at update time.