The Substring-Matching Template

What is this?

Think of the window as a spotlight that can both widen and narrow. You first stretch its right edge outward until it covers everything you need, then squeeze its left edge inward to trim away anything wasteful — keeping the best window you have seen along the way. This one breathing motion, expand then contract, solves a surprising number of "find the smallest or longest stretch" problems with the same short piece of code.

💡 Fun fact: This expand-then-contract template is the same shape behind real-time search-and-highlight features and DNA motif scanners in bioinformatics, which hunt for the shortest stretch of a genome containing a given set of markers.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Almost every hard sliding-window problem fits one template: grow the window on the right until it satisfies a condition, then shrink it from the left while it stays satisfied, recording the best as you go. Learn this ~10-line shape once and Minimum Window Substring, Longest Substring Without Repeating, and their cousins all become fill-in-the-blanks.

The template

need = Counter(t)          # what the window must contain (problem-specific)
have, required = 0, len(need)
left = 0
for right, ch in enumerate(s):
    # 1) include s[right] in the window state
    if ch in need:
        need[ch] -= 1
        if need[ch] == 0: have += 1
    # 2) while the window is VALID, try to shrink and record the answer
    while have == required:
        update_answer(left, right)
        lch = s[left]
        if lch in need:
            if need[lch] == 0: have -= 1
            need[lch] += 1
        left += 1

Only three things change per problem: what state the window tracks, what "valid" means, and whether you record on growth (longest) or on shrink (shortest).

The problems

• Minimum Window Substring — the template at full strength: a need/have counter finds the smallest window containing all of t.
• Longest Substring Without Repeating Characters — the validity is "no duplicate"; the last-seen-index trick jumps the left edge in O(1).

Key takeaways

• One template: expand right to validity, contract left to optimality, record as you go.
• Customize three things: the window state, the validity test, and record-on-grow vs record-on-shrink.
• A required/formed counter makes validity O(1).
• Last-seen-index lets "no repeats" jump the left edge instead of stepping.
• Why interviewers love it: recognizing that a new problem is this template is the senior move.

Start here: Minimum Window Substring (the full template), then Longest Substring Without Repeating Characters.