Window Shrinking Logic

Shrinking logic is the careful reasoning about when and how much to shrink: sometimes one step, sometimes jump L to last_index[ch]+1 for uniqueness shortcuts.

Why this shows up in the real world

Calendar scheduling might snap a meeting window start forward to the next free slot—discrete jumps, not +1 every time.

Core idea (explained for students)

Compare incremental shrink vs monotonic queue shrink for min-in-window. For duplicates, storing last occurrence maps enables batch jumps of L.

Try this in Python

def length_longest_substring_two_distinct(s: str) -> int:
    from collections import Counter

    ct, L, best = Counter(), 0, 0
    for R, ch in enumerate(s):
        ct[ch] += 1
        while len(ct) > 2:
            ct[s[L]] -= 1
            if ct[s[L]] == 0:
                del ct[s[L]]
            L += 1
        best = max(best, R - L + 1)
    return best


print(length_longest_substring_two_distinct("eceba"))

Common mistakes

• Jumping L without proving no valid window was skipped.
• Mixing two different shrink policies in one problem.

Key takeaways

• Write the invariant sentence: “Smallest L such that…”
• Jump tricks need formal justification in contests.