Common String Patterns - Learning Module

Loading content...

0/276

Sliding Window Intuition

The Window Metaphor

Imagine looking at a string through a narrow window that can slide left to right. At any moment, you can only see the characters inside the window. As the window slides, some characters leave your view while new ones enter. This is the sliding window technique—a powerful pattern for problems involving contiguous substrings.

Sliding window builds directly on co-moving two-pointer techniques, but with a specific focus: maintaining and processing a contiguous range (or "window") that moves through the string. The left edge of the window contracts it; the right edge expands it. What happens inside the window determines the solution.

This page develops your intuition for sliding window problems on strings. We'll focus on understanding when this technique applies and how to think about window mechanics, preparing you for rigorous algorithm study later.

What You Will Learn

By the end of this page, you will understand the sliding window mental model, distinguish between fixed-size and variable-size windows, recognize problem characteristics that signal sliding window applicability, and grasp how window state is maintained efficiently using incremental updates.

What Is a Sliding Window?

A sliding window is a contiguous range within a string (or array) defined by two pointers—left and right—that "slide" through the data.

The Window:

Left boundary (L): The start of the current window
Right boundary (R): The end of the current window
Window content: Characters from index L to R (inclusive or exclusive, depending on convention)
Window size: R - L (for half-open) or R - L + 1 (for closed interval)

The Sliding Action:

As we process the string:

Expand: Move R to the right, adding a new character to the window
Contract: Move L to the right, removing a character from the window
Slide: Both boundaries move, maintaining constant size

The art of sliding window problems is knowing when to expand and when to contract.

Visual Representation:

String: a b c d e f g h i j
        0 1 2 3 4 5 6 7 8 9

Window at time T1:  [L=2, R=5)
        a b [c d e] f g h i j
              ^^^^^
              Window contains "cde"

Window at time T2 (after sliding):  [L=4, R=7)
        a b c d [e f g] h i j
                  ^^^^^
                  Window contains "efg"

The window has "slid" from one contiguous substring to another. The characters that left (c, d) are no longer considered; the characters that entered (f, g) are now included.

Connection to Two Pointers

Sliding window is a specialized form of co-moving two pointers. Both pointers move in the same direction (left to right), but they maintain a relationship: they define the boundaries of a meaningful range. The "window state" encapsulates what we care about within that range.

Fixed-Size Windows

The simplest form of sliding window has a fixed size. The window is always exactly k characters wide, and it slides through the string examining every contiguous substring of length k.

Fixed Window Mechanics:

Initialize: Window covers positions [0, k)
Process the initial window
Slide: For each step, remove character at left, add character at right
The window now covers [1, k+1), then [2, k+2), and so on

Example: Find All Anagrams of Pattern P in Text T

Given text T and pattern P of length k, find all starting positions where T contains an anagram of P.

Approach:

Window size = k (length of pattern)
Slide the window through T
For each window position, check if the window's character frequencies match P's frequencies
If so, record the starting position

fixed_window_intuition

Conceptual Algorithm

FindAnagramPositions(T, P):
    k = length(P)
    n = length(T)
    
    IF k > n:
        RETURN empty list
    
    // Build frequency map for pattern
    targetFreq = buildFrequency(P)
    
    // Build frequency map for initial window
    windowFreq = buildFrequency(T[0:k])
    
    result = empty list
    
    // Check initial window
    IF windowFreq == targetFreq:
        result.add(0)
    
    // Slide the window
    FOR i = k TO n - 1:
        // Add character entering window (at position i)
        windowFreq[T[i]] += 1
        
        // Remove character leaving window (at position i - k)
        windowFreq[T[i - k]] -= 1
        IF windowFreq[T[i - k]] == 0:
            remove T[i - k] from windowFreq
        
        // Check if current window matches
        IF windowFreq == targetFreq:
            result.add(i - k + 1)   // Starting position of this window
    
    RETURN result

Why This Works:

We examine all (n - k + 1) windows of size k
Each window is updated incrementally: O(1) to add one character and remove one character
Total time: O(n) for sliding + O(k) for initial setup = O(n + k)

Without Sliding Window:

A naive approach would rebuild the frequency map for each window from scratch:

O(k) per window × (n - k + 1) windows = O(nk) time

Sliding window achieves O(n) by reusing work—the key insight is that adjacent windows share k-1 characters.

The Reuse Principle

Fixed-size sliding windows exploit massive overlap between consecutive windows. Window [i, i+k) and window [i+1, i+k+1) share k-1 characters. Recomputing from scratch wastes this overlap. Incremental updates (add one, remove one) leverage it for O(1) transitions.

Variable-Size Windows

More interesting problems involve variable-size windows—windows that grow and shrink based on conditions. These problems ask for the longest, shortest, or optimal window satisfying some constraint.

Variable Window Mechanics:

Start with an empty or minimal window (L = R = 0)
Expand by moving R right, adding T[R] to the window
After each expansion, check if the window satisfies or violates a condition
Contract by moving L right until the condition is restored
Track the optimal window found during this process

The Expand-Contract Dance:

FOR R = 0 TO n - 1:
    // Expand: include T[R] in window
    updateWindowState(add T[R])
    
    WHILE window violates condition:
        // Contract: remove T[L] from window
        updateWindowState(remove T[L])
        L += 1
    
    // Window [L, R] now satisfies condition
    // Update answer if this window is optimal

Example: Longest Substring Without Repeating Characters

Find the length of the longest substring with all unique characters.

Condition: Window is valid when all characters in it are unique (no duplicates).

Expand: Always move R to add the next character.

Contract: If the new character creates a duplicate, move L until the duplicate is removed.

Track: The maximum window size (R - L + 1) seen when window is valid.

Trace for "abcabcbb":

R	Char	Window After Add	Valid?	Contract?	Window After Contract	Max
0	a	[a]	Yes	No	[a]	1
1	b	[a,b]	Yes	No	[a,b]	2
2	c	[a,b,c]	Yes	No	[a,b,c]	3
3	a	[a,b,c,a]	No (dup a)	Yes	[b,c,a]	3
4	b	[b,c,a,b]	No (dup b)	Yes	[c,a,b]	3
5	c	[c,a,b,c]	No (dup c)	Yes	[a,b,c]	3
6	b	[a,b,c,b]	No (dup b)	Yes	[c,b]	3
7	b	[c,b,b]	No (dup b)	Yes	[b]	3

Answer: 3 (substring "abc")

The Monotonicity Insight

Variable-size windows work because of monotonicity: if a window is invalid, making it larger won't fix it (for problems like 'all unique'). Conversely, making it smaller might restore validity. This monotonicity justifies the expand-until-invalid, contract-until-valid strategy.

Window State Maintenance

The efficiency of sliding window algorithms depends on how we maintain window state—the information needed to evaluate conditions and update answers.

Common State Types:

1. Character Frequency Map

Track how many times each character appears in the current window.

Operations:

Add character c: freq[c] += 1
Remove character c: freq[c] -= 1
Both are O(1)

Use cases: Anagram finding, character coverage, duplicate detection.

2. Sum/Aggregate

For problems involving character values (e.g., sum of ASCII values).

Operations:

Add character c: sum += value(c)
Remove character c: sum -= value(c)

Use cases: Substring sums, average calculations.

3. Distinct Count

Track the number of distinct characters in the window.

Operations:

Add character c: if freq[c] == 0: distinctCount += 1; freq[c] += 1
Remove character c: freq[c] -= 1; if freq[c] == 0: distinctCount -= 1
O(1) with careful bookkeeping

Use cases: "At most k distinct characters," "exactly k distinct characters."

4. Validity Counter

For problems like "window contains all characters of pattern," track how many distinct required characters are fully covered.

Operations:

When adding makes windowFreq[c] == targetFreq[c]: formed += 1
When removing makes windowFreq[c] < targetFreq[c]: formed -= 1
Window is valid when formed == requiredDistinct

Use cases: Minimum window substring, permutation in string.

State Design Is Key

The hardest part of sliding window problems is often designing the right state. Ask: What do I need to know about the window to check the condition? Can I update this information in O(1) when adding/removing one character? If yes, sliding window likely works. If state requires O(k) to update, reconsider your approach.

Common Window State Patterns
State Type	Add Operation	Remove Operation	Space
Frequency Map	freq[c]++	freq[c]--	O(\|Σ\|)
Sum/Aggregate	sum += val(c)	sum -= val(c)	O(1)
Distinct Count	if 0→1: count++	if 1→0: count--	O(\|Σ\|)
Coverage Counter	if match: formed++	if unmatch: formed--	O(\|Σ\|)
Min/Max (complex)	Use monotonic deque	Pop from deque	O(k)

Recognizing Sliding Window Problems

Recognizing when sliding window applies is a crucial skill. Look for these signals:

Signal 1: Contiguous Substring/Subarray Required

Keywords: "contiguous," "substring," "subarray," "consecutive"

If the problem asks about contiguous portions of the input, sliding window might apply. (Contrast with "subsequence," which is non-contiguous and typically needs different techniques.)

Signal 2: Optimization Over All Windows

Keywords: "longest," "shortest," "minimum," "maximum," "find the length of"

Problems asking for the best (longest/shortest) contiguous range satisfying a condition are prime sliding window candidates.

Signal 3: Counting Windows

Keywords: "count how many subarrays," "find all substrings that"

Counting all windows satisfying a condition often uses sliding window with careful counting logic.

Signal 4: Condition on Window Content

Keywords: "contains all," "at most k," "exactly k," "without repeating," "with equal number of"

Conditions about what the window must or must not contain are sliding window indicators. The condition determines when to expand vs. contract.

Signal 5: Fixed-Size Pattern Matching

Keywords: "of length k," "substrings of size k," "every window of size"

Explicit window size suggests fixed-size sliding window. Simple to implement once recognized.

Problem Pattern Recognition

•"Longest substring without repeating characters" → Variable window, shrink on duplicate
•"Find all anagrams of pattern in text" → Fixed window (size = pattern length)
•"Minimum window containing all characters of pattern" → Variable window, find minimum valid
•"Maximum sum subarray of size k" → Fixed window, track sum
•"Longest substring with at most k distinct characters" → Variable window, shrink when > k
•"Count subarrays with exactly k distinct elements" → Use 'exactly k = at most k - at most k-1' trick
•"Longest repeating character replacement with at most k changes" → Variable window with character frequency
•"Permutation in string" → Fixed window, frequency matching

When Sliding Window Doesn't Apply

Sliding window fails when: (1) The problem involves non-contiguous elements (use subsequence techniques instead), (2) The condition isn't monotonic (expanding might fix a problem), (3) You need to track relationships that can't be updated incrementally. Force-fitting sliding window to these problems leads to incorrect solutions.

The Minimum Window Substring Pattern

One of the most important sliding window problems is "Minimum Window Substring": find the shortest substring of S that contains all characters of T. This problem illustrates sophisticated window management.

The Challenge:

We need all characters from T (with correct frequencies)
We want the smallest such window
Characters can appear in any order

The Strategy:

Expand right until window contains all characters of T (window becomes "valid")
Contract left while window remains valid, tracking the minimum size
Continue expanding to find other valid windows

The key insight: we maintain both when the window is valid and track the minimum among all valid windows.

min_window_substring_intuition

Conceptual Algorithm

MinWindowSubstring(S, T):
    IF length(T) > length(S):
        RETURN ""
    
    // Target frequencies we need to satisfy
    targetFreq = buildFrequency(T)
    required = number of distinct chars in T
    
    // Window state
    windowFreq = empty frequency map
    formed = 0          // How many distinct chars are fully covered
    
    // Answer tracking
    minLength = infinity
    minStart = 0
    
    L = 0
    
    FOR R = 0 TO length(S) - 1:
        // Expand: add S[R] to window
        c = S[R]
        windowFreq[c] += 1
        
        // Check if this char is now fully covered
        IF c in targetFreq AND windowFreq[c] == targetFreq[c]:
            formed += 1
        
        // Contract while window is valid
        WHILE formed == required:
            // Current window is valid; check if it's minimal
            IF R - L + 1 < minLength:
                minLength = R - L + 1
                minStart = L
            
            // Remove S[L] from window
            leftChar = S[L]
            windowFreq[leftChar] -= 1
            IF leftChar in targetFreq AND windowFreq[leftChar] < targetFreq[leftChar]:
                formed -= 1
            L += 1
    
    IF minLength == infinity:
        RETURN ""
    RETURN S[minStart : minStart + minLength]

Why This Pattern Is Important:

This algorithm demonstrates:

Two counters: required (static target) and formed (dynamic window state)
Validity check: formed == required means window contains all needed characters
Minimize while valid: Contract as much as possible while staying valid to find the minimum
O(n) time: Each character is added once, removed once

Once you master this pattern, many similar problems become straightforward variations.

The 'Formed' Counter Technique

Rather than comparing full frequency maps (O(|Σ|) per check), we track 'formed'—the count of fully satisfied character requirements. When formed equals the number of distinct characters needed, the window is valid. This O(1) validity check is what makes the algorithm efficient.

Common Pitfalls and Edge Cases

Sliding window algorithms are prone to specific bugs. Awareness prevents wasted debugging time.

Pitfall 1: Off-By-One in Window Size

For a window [L, R):

Size = R - L
For a window [L, R] (inclusive):
Size = R - L + 1

Choose one convention and stick to it. Mixing conventions causes bugs.

Pitfall 2: Forgetting to Remove Zero-Count Entries

When comparing frequency maps:

{a: 2, b: 0} should equal {a: 2} for most problems
But the maps aren't structurally equal unless you remove the zero
Either normalize before comparison or use the 'formed' counter approach

Pitfall 3: Incorrect Contraction

Contracting should stop when the window becomes invalid (for 'find minimum valid')
Contracting should continue while window stays valid (need to check condition on both sides of the loop boundary)
Getting this boundary wrong misses optimal answers

Pitfall 4: Not Updating Answer at the Right Time

For 'longest valid window': Update answer when window is valid before contracting. For 'shortest valid window': Update answer when window first becomes valid, then again after each contraction if still valid.

Edge Cases to Handle

•Empty input string: Return 0 or "" as appropriate
•Pattern longer than text: No valid window exists
•Single character: Window of size 1, trivially valid or invalid
•All same characters: May be entirely valid or need special handling
•No valid window exists: Return -1, 0, or "" depending on problem requirements
•Multiple optimal windows: Problem may ask for first, last, or count
•Characters in pattern not in text: No valid window possible

Test Your Boundaries

Before submitting, trace through: (1) a minimal valid case (pattern == text), (2) a case with no valid window, (3) a case where the optimal window is at the very end, (4) a case where the optimal window is the entire string. These catches most boundary bugs.

Complexity Analysis

Sliding window algorithms achieve excellent time complexity through incremental updates.

Time Complexity: O(n)

Both fixed and variable-size sliding windows are O(n):

Fixed-size (window size k):

O(k) to set up initial window
O(1) per slide (add one, remove one) × (n - k) slides
Total: O(n)

Variable-size:

Right pointer visits each position exactly once: n iterations
Left pointer visits each position at most once: at most n movements total
Each character is added and removed at most once
Total: O(n) + O(n) = O(n)

The Amortization Argument

The variable-size sliding window is O(n) despite the nested while loop because L never moves backward. Over the entire algorithm, L moves right at most n times total. This amortization across all iterations gives O(n), not O(n²).

Sliding Window Complexity Summary
Variant	Time	Space	Notes
Fixed-size window	O(n)	O(k) or O(\|Σ\|)	k = window size
Variable-size window	O(n)	O(\|Σ\|)	State space typically O(\|Σ\|)
Naive recompute each window	O(n × k)	O(k)	For comparison
Brute force all substrings	O(n² × check)	O(1) to O(n)	Much slower

Space Complexity: O(|Σ|) or O(k)

Space depends on window state:

Frequency map: O(|Σ|) where |Σ| is alphabet size
For fixed k ASCII characters: O(1) since 128 is constant
If tracking positions or using auxiliary structures: may be O(k)

Comparison with Alternatives:

Approach	Time	Space	When to Use
Sliding window	O(n)	O(	Σ
Two pointers (non-window)	O(n)	O(1)	Pairs, not ranges
Hash all substrings	O(n² × hash)	O(n²)	Need to store all substrings
Suffix array + LCP	O(n log n)	O(n)	Complex substring queries

Connecting the Patterns

Let's connect sliding window to the other patterns we've learned in this module:

Sliding Window + Frequency Counting

Many sliding window problems use frequency counting as the window state:

Track character frequencies in the current window
Add/remove characters incrementally
Compare window frequencies to target frequencies

The two techniques are deeply complementary.

Sliding Window + Prefix/Suffix

Fixed windows of size k are essentially adjacent prefixes of suffixes:

Window [i, i+k) = suffix starting at i, truncated to length k
Understanding this connection helps with advanced techniques like suffix arrays

Sliding Window + Two Pointers

Sliding window IS two pointers with a specific structure:

Left and right pointers define the window
Movement rules depend on window validity
The "window" metaphor adds semantic meaning to the two-pointer framework

The Pattern Evolution:

1. Single Index Traversal
   ↓
2. Two Pointers (generic)
   ↓
3. Sliding Window (specialized two-pointer for ranges)
   ↓
4. Sliding Window + Frequency State
   ↓
5. Advanced Structures (monotonic deques, etc.)

Each level builds on the previous. Mastering sliding window prepares you for more advanced techniques like:

Monotonic deque for sliding window min/max
Segment trees for complex range queries
Deamortized sliding window using two stacks

The Unified View

All these patterns—frequency counting, prefix/suffix analysis, two pointers, sliding window—are different lenses for viewing string problems. Expert problem solvers rapidly switch between lenses, combining them as needed. The goal isn't to memorize templates but to internalize the core ideas deeply enough to combine them fluidly.

Summary and Key Takeaways

We've built intuition for sliding window—one of the most powerful techniques for string (and array) problems involving contiguous ranges. Let's consolidate the key insights:

Core Concepts Mastered

•The window metaphor: Two pointers defining a contiguous range that slides through the string
•Fixed-size windows: Constant size, simple slide operation, good for pattern matching
•Variable-size windows: Expand-then-contract strategy for optimization problems
•Window state: Incrementally maintained (add/remove in O(1)) for efficiency
•O(n) time: Each element added once, removed once; nested loops are amortized
•The 'formed' counter: O(1) validity checking instead of O(|Σ|) map comparison
•Recognition signals: Contiguous, longest/shortest, contains/cover conditions

Module Complete

This module has equipped you with four fundamental patterns for string problem-solving: character frequency counting (composition view), prefixes/suffixes/substrings (structure view), two-pointer techniques (pair processing), and sliding window (range processing). These patterns appear throughout algorithm problems and form the foundation for advanced string algorithms like KMP, Rabin-Karp, suffix arrays, and more.

Page Complete

You now understand sliding window at an intuitive level—what it is, when it applies, how to maintain window state, and the key patterns like minimum window substring. Combined with the other techniques from this module, you have a powerful toolkit for tackling string problems. Practice these patterns on real problems to solidify your intuition.

Sliding Window Intuition

The Window Metaphor

What You Will Learn

What Is a Sliding Window?

A sliding window is a contiguous range within a string (or array) defined by two pointers—left and right—that "slide" through the data.

The Window:

Left boundary (L): The start of the current window
Right boundary (R): The end of the current window
Window content: Characters from index L to R (inclusive or exclusive, depending on convention)
Window size: R - L (for half-open) or R - L + 1 (for closed interval)

The Sliding Action:

As we process the string:

Expand: Move R to the right, adding a new character to the window
Contract: Move L to the right, removing a character from the window
Slide: Both boundaries move, maintaining constant size

The art of sliding window problems is knowing when to expand and when to contract.

Visual Representation:

String: a b c d e f g h i j
        0 1 2 3 4 5 6 7 8 9

Window at time T1:  [L=2, R=5)
        a b [c d e] f g h i j
              ^^^^^
              Window contains "cde"

Window at time T2 (after sliding):  [L=4, R=7)
        a b c d [e f g] h i j
                  ^^^^^
                  Window contains "efg"

The window has "slid" from one contiguous substring to another. The characters that left (c, d) are no longer considered; the characters that entered (f, g) are now included.

Connection to Two Pointers

Fixed-Size Windows

The simplest form of sliding window has a fixed size. The window is always exactly k characters wide, and it slides through the string examining every contiguous substring of length k.

Fixed Window Mechanics:

Initialize: Window covers positions [0, k)
Process the initial window
Slide: For each step, remove character at left, add character at right
The window now covers [1, k+1), then [2, k+2), and so on

Example: Find All Anagrams of Pattern P in Text T

Given text T and pattern P of length k, find all starting positions where T contains an anagram of P.

Approach:

Window size = k (length of pattern)
Slide the window through T
For each window position, check if the window's character frequencies match P's frequencies
If so, record the starting position

fixed_window_intuition

Conceptual Algorithm

FindAnagramPositions(T, P):
    k = length(P)
    n = length(T)
    
    IF k > n:
        RETURN empty list
    
    // Build frequency map for pattern
    targetFreq = buildFrequency(P)
    
    // Build frequency map for initial window
    windowFreq = buildFrequency(T[0:k])
    
    result = empty list
    
    // Check initial window
    IF windowFreq == targetFreq:
        result.add(0)
    
    // Slide the window
    FOR i = k TO n - 1:
        // Add character entering window (at position i)
        windowFreq[T[i]] += 1
        
        // Remove character leaving window (at position i - k)
        windowFreq[T[i - k]] -= 1
        IF windowFreq[T[i - k]] == 0:
            remove T[i - k] from windowFreq
        
        // Check if current window matches
        IF windowFreq == targetFreq:
            result.add(i - k + 1)   // Starting position of this window
    
    RETURN result

Why This Works:

We examine all (n - k + 1) windows of size k
Each window is updated incrementally: O(1) to add one character and remove one character
Total time: O(n) for sliding + O(k) for initial setup = O(n + k)

Without Sliding Window:

A naive approach would rebuild the frequency map for each window from scratch:

O(k) per window × (n - k + 1) windows = O(nk) time

Sliding window achieves O(n) by reusing work—the key insight is that adjacent windows share k-1 characters.

The Reuse Principle

Variable-Size Windows

Variable Window Mechanics:

Start with an empty or minimal window (L = R = 0)
Expand by moving R right, adding T[R] to the window
After each expansion, check if the window satisfies or violates a condition
Contract by moving L right until the condition is restored
Track the optimal window found during this process

The Expand-Contract Dance:

FOR R = 0 TO n - 1:
    // Expand: include T[R] in window
    updateWindowState(add T[R])
    
    WHILE window violates condition:
        // Contract: remove T[L] from window
        updateWindowState(remove T[L])
        L += 1
    
    // Window [L, R] now satisfies condition
    // Update answer if this window is optimal

Example: Longest Substring Without Repeating Characters

Find the length of the longest substring with all unique characters.

Condition: Window is valid when all characters in it are unique (no duplicates).

Expand: Always move R to add the next character.

Contract: If the new character creates a duplicate, move L until the duplicate is removed.

Track: The maximum window size (R - L + 1) seen when window is valid.

Trace for "abcabcbb":

R	Char	Window After Add	Valid?	Contract?	Window After Contract	Max
0	a	[a]	Yes	No	[a]	1
1	b	[a,b]	Yes	No	[a,b]	2
2	c	[a,b,c]	Yes	No	[a,b,c]	3
3	a	[a,b,c,a]	No (dup a)	Yes	[b,c,a]	3
4	b	[b,c,a,b]	No (dup b)	Yes	[c,a,b]	3
5	c	[c,a,b,c]	No (dup c)	Yes	[a,b,c]	3
6	b	[a,b,c,b]	No (dup b)	Yes	[c,b]	3
7	b	[c,b,b]	No (dup b)	Yes	[b]	3

Answer: 3 (substring "abc")

The Monotonicity Insight

Window State Maintenance

The efficiency of sliding window algorithms depends on how we maintain window state—the information needed to evaluate conditions and update answers.

Common State Types:

1. Character Frequency Map

Track how many times each character appears in the current window.

Operations:

Add character c: freq[c] += 1
Remove character c: freq[c] -= 1
Both are O(1)

Use cases: Anagram finding, character coverage, duplicate detection.

2. Sum/Aggregate

For problems involving character values (e.g., sum of ASCII values).

Operations:

Add character c: sum += value(c)
Remove character c: sum -= value(c)

Use cases: Substring sums, average calculations.

3. Distinct Count

Track the number of distinct characters in the window.

Operations:

Add character c: if freq[c] == 0: distinctCount += 1; freq[c] += 1
Remove character c: freq[c] -= 1; if freq[c] == 0: distinctCount -= 1
O(1) with careful bookkeeping

Use cases: "At most k distinct characters," "exactly k distinct characters."

4. Validity Counter

For problems like "window contains all characters of pattern," track how many distinct required characters are fully covered.

Operations:

When adding makes windowFreq[c] == targetFreq[c]: formed += 1
When removing makes windowFreq[c] < targetFreq[c]: formed -= 1
Window is valid when formed == requiredDistinct

Use cases: Minimum window substring, permutation in string.

State Design Is Key

Common Window State Patterns
State Type	Add Operation	Remove Operation	Space
Frequency Map	freq[c]++	freq[c]--	O(\|Σ\|)
Sum/Aggregate	sum += val(c)	sum -= val(c)	O(1)
Distinct Count	if 0→1: count++	if 1→0: count--	O(\|Σ\|)
Coverage Counter	if match: formed++	if unmatch: formed--	O(\|Σ\|)
Min/Max (complex)	Use monotonic deque	Pop from deque	O(k)

Recognizing Sliding Window Problems

Recognizing when sliding window applies is a crucial skill. Look for these signals:

Signal 1: Contiguous Substring/Subarray Required

Keywords: "contiguous," "substring," "subarray," "consecutive"

If the problem asks about contiguous portions of the input, sliding window might apply. (Contrast with "subsequence," which is non-contiguous and typically needs different techniques.)

Signal 2: Optimization Over All Windows

Keywords: "longest," "shortest," "minimum," "maximum," "find the length of"

Problems asking for the best (longest/shortest) contiguous range satisfying a condition are prime sliding window candidates.

Signal 3: Counting Windows

Keywords: "count how many subarrays," "find all substrings that"

Counting all windows satisfying a condition often uses sliding window with careful counting logic.

Signal 4: Condition on Window Content

Keywords: "contains all," "at most k," "exactly k," "without repeating," "with equal number of"

Conditions about what the window must or must not contain are sliding window indicators. The condition determines when to expand vs. contract.

Signal 5: Fixed-Size Pattern Matching

Keywords: "of length k," "substrings of size k," "every window of size"

Explicit window size suggests fixed-size sliding window. Simple to implement once recognized.

Problem Pattern Recognition

•"Longest substring without repeating characters" → Variable window, shrink on duplicate
•"Find all anagrams of pattern in text" → Fixed window (size = pattern length)
•"Minimum window containing all characters of pattern" → Variable window, find minimum valid
•"Maximum sum subarray of size k" → Fixed window, track sum
•"Longest substring with at most k distinct characters" → Variable window, shrink when > k
•"Count subarrays with exactly k distinct elements" → Use 'exactly k = at most k - at most k-1' trick
•"Longest repeating character replacement with at most k changes" → Variable window with character frequency
•"Permutation in string" → Fixed window, frequency matching

When Sliding Window Doesn't Apply

The Minimum Window Substring Pattern

The Challenge:

We need all characters from T (with correct frequencies)
We want the smallest such window
Characters can appear in any order

The Strategy:

Expand right until window contains all characters of T (window becomes "valid")
Contract left while window remains valid, tracking the minimum size
Continue expanding to find other valid windows

The key insight: we maintain both when the window is valid and track the minimum among all valid windows.

min_window_substring_intuition

Conceptual Algorithm

MinWindowSubstring(S, T):
    IF length(T) > length(S):
        RETURN ""
    
    // Target frequencies we need to satisfy
    targetFreq = buildFrequency(T)
    required = number of distinct chars in T
    
    // Window state
    windowFreq = empty frequency map
    formed = 0          // How many distinct chars are fully covered
    
    // Answer tracking
    minLength = infinity
    minStart = 0
    
    L = 0
    
    FOR R = 0 TO length(S) - 1:
        // Expand: add S[R] to window
        c = S[R]
        windowFreq[c] += 1
        
        // Check if this char is now fully covered
        IF c in targetFreq AND windowFreq[c] == targetFreq[c]:
            formed += 1
        
        // Contract while window is valid
        WHILE formed == required:
            // Current window is valid; check if it's minimal
            IF R - L + 1 < minLength:
                minLength = R - L + 1
                minStart = L
            
            // Remove S[L] from window
            leftChar = S[L]
            windowFreq[leftChar] -= 1
            IF leftChar in targetFreq AND windowFreq[leftChar] < targetFreq[leftChar]:
                formed -= 1
            L += 1
    
    IF minLength == infinity:
        RETURN ""
    RETURN S[minStart : minStart + minLength]

Why This Pattern Is Important:

This algorithm demonstrates:

Two counters: required (static target) and formed (dynamic window state)
Validity check: formed == required means window contains all needed characters
Minimize while valid: Contract as much as possible while staying valid to find the minimum
O(n) time: Each character is added once, removed once

Once you master this pattern, many similar problems become straightforward variations.

The 'Formed' Counter Technique

Common Pitfalls and Edge Cases

Sliding window algorithms are prone to specific bugs. Awareness prevents wasted debugging time.

Pitfall 1: Off-By-One in Window Size

For a window [L, R):

Size = R - L
For a window [L, R] (inclusive):
Size = R - L + 1

Choose one convention and stick to it. Mixing conventions causes bugs.

Pitfall 2: Forgetting to Remove Zero-Count Entries

When comparing frequency maps:

{a: 2, b: 0} should equal {a: 2} for most problems
But the maps aren't structurally equal unless you remove the zero
Either normalize before comparison or use the 'formed' counter approach

Pitfall 3: Incorrect Contraction

Contracting should stop when the window becomes invalid (for 'find minimum valid')
Contracting should continue while window stays valid (need to check condition on both sides of the loop boundary)
Getting this boundary wrong misses optimal answers

Pitfall 4: Not Updating Answer at the Right Time

Edge Cases to Handle

•Empty input string: Return 0 or "" as appropriate
•Pattern longer than text: No valid window exists
•Single character: Window of size 1, trivially valid or invalid
•All same characters: May be entirely valid or need special handling
•No valid window exists: Return -1, 0, or "" depending on problem requirements
•Multiple optimal windows: Problem may ask for first, last, or count
•Characters in pattern not in text: No valid window possible

Test Your Boundaries

Complexity Analysis

Sliding window algorithms achieve excellent time complexity through incremental updates.

Time Complexity: O(n)

Both fixed and variable-size sliding windows are O(n):

Fixed-size (window size k):

O(k) to set up initial window
O(1) per slide (add one, remove one) × (n - k) slides
Total: O(n)

Variable-size:

Right pointer visits each position exactly once: n iterations
Left pointer visits each position at most once: at most n movements total
Each character is added and removed at most once
Total: O(n) + O(n) = O(n)

The Amortization Argument

Sliding Window Complexity Summary
Variant	Time	Space	Notes
Fixed-size window	O(n)	O(k) or O(\|Σ\|)	k = window size
Variable-size window	O(n)	O(\|Σ\|)	State space typically O(\|Σ\|)
Naive recompute each window	O(n × k)	O(k)	For comparison
Brute force all substrings	O(n² × check)	O(1) to O(n)	Much slower

Space Complexity: O(|Σ|) or O(k)

Space depends on window state:

Frequency map: O(|Σ|) where |Σ| is alphabet size
For fixed k ASCII characters: O(1) since 128 is constant
If tracking positions or using auxiliary structures: may be O(k)

Comparison with Alternatives:

Approach	Time	Space	When to Use
Sliding window	O(n)	O(	Σ
Two pointers (non-window)	O(n)	O(1)	Pairs, not ranges
Hash all substrings	O(n² × hash)	O(n²)	Need to store all substrings
Suffix array + LCP	O(n log n)	O(n)	Complex substring queries

Connecting the Patterns

Let's connect sliding window to the other patterns we've learned in this module:

Sliding Window + Frequency Counting

Many sliding window problems use frequency counting as the window state:

Track character frequencies in the current window
Add/remove characters incrementally
Compare window frequencies to target frequencies

The two techniques are deeply complementary.

Sliding Window + Prefix/Suffix

Fixed windows of size k are essentially adjacent prefixes of suffixes:

Window [i, i+k) = suffix starting at i, truncated to length k
Understanding this connection helps with advanced techniques like suffix arrays

Sliding Window + Two Pointers

Sliding window IS two pointers with a specific structure:

Left and right pointers define the window
Movement rules depend on window validity
The "window" metaphor adds semantic meaning to the two-pointer framework

The Pattern Evolution:

1. Single Index Traversal
   ↓
2. Two Pointers (generic)
   ↓
3. Sliding Window (specialized two-pointer for ranges)
   ↓
4. Sliding Window + Frequency State
   ↓
5. Advanced Structures (monotonic deques, etc.)

Each level builds on the previous. Mastering sliding window prepares you for more advanced techniques like:

Monotonic deque for sliding window min/max
Segment trees for complex range queries
Deamortized sliding window using two stacks

The Unified View

Summary and Key Takeaways

We've built intuition for sliding window—one of the most powerful techniques for string (and array) problems involving contiguous ranges. Let's consolidate the key insights:

Core Concepts Mastered

•The window metaphor: Two pointers defining a contiguous range that slides through the string
•Fixed-size windows: Constant size, simple slide operation, good for pattern matching
•Variable-size windows: Expand-then-contract strategy for optimization problems
•Window state: Incrementally maintained (add/remove in O(1)) for efficiency
•O(n) time: Each element added once, removed once; nested loops are amortized
•The 'formed' counter: O(1) validity checking instead of O(|Σ|) map comparison
•Recognition signals: Contiguous, longest/shortest, contains/cover conditions

Module Complete

Page Complete