Sliding Window on Strings: Patterns and Templates

The sliding window is one of the most powerful patterns for string problems. Instead of checking every possible substring (which is O(n^2) or worse), you maintain a window that expands and contracts as you scan left to right. The result is usually an O(n) solution that feels almost magical once you see the template.

Why sliding window works on strings

Strings are sequences, and many problems ask you to find a substring that satisfies some condition — the longest one, the shortest one, or all positions where one exists. Brute force generates every substring, checks each, and takes O(n^2) or O(n^3) time. The sliding window avoids this by maintaining two pointers — left and right — and a state object (usually a hash map) that tracks what is inside the current window.

The key insight: when you expand right, you add one character. When you shrink left, you remove one character. Each character enters and leaves the window at most once, so the total work is O(n).

The two flavors

Fixed-size window

The window has a known length k. You slide it across the string one position at a time. Useful for anagram detection and problems where the substring length is given.

Variable-size window

The window grows and shrinks to find the optimal substring. You expand right until a condition is met, then shrink left to tighten. This handles “longest substring” and “minimum window” problems.

The universal template

Here is the template that covers most variable-size window problems:

def sliding_window(s: str) -> int:
    from collections import defaultdict

    freq = defaultdict(int)
    left = 0
    result = 0  # or float('inf') for minimum problems

    for right in range(len(s)):
        # 1. Expand: add s[right] to window state
        freq[s[right]] += 1

        # 2. Shrink: while the window is invalid, remove s[left]
        while window_is_invalid(freq):
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1

        # 3. Update result
        result = max(result, right - left + 1)

    return result

The only parts that change between problems are:

1. What state you track — frequency map, count of distinct chars, etc.
2. When the window is invalid — too many distinct chars, missing a required char, etc.
3. How you update the result — max length, min length, collect positions, etc.

Problem 1: Longest Substring Without Repeating Characters

LeetCode 3. Given a string s, find the length of the longest substring without repeating characters.

Approach

Use a variable-size window. The window is invalid when any character appears more than once. Track character frequencies in a hash map.

def length_of_longest_substring(s: str) -> int:
    freq = {}
    left = 0
    max_len = 0

    for right in range(len(s)):
        ch = s[right]
        freq[ch] = freq.get(ch, 0) + 1

        # Shrink while we have a duplicate
        while freq[ch] > 1:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

Walkthrough

For s = "abcabcbb":

• Window grows: a, ab, abc — all unique, max_len = 3.
• right hits second a: freq of a becomes 2. Shrink left past the first a. Window is now bca, max_len stays 3.
• Continue until end. Answer is 3.

Optimized version with last-seen index

Instead of shrinking one step at a time, jump left directly to the position after the last occurrence:

def length_of_longest_substring_optimized(s: str) -> int:
    last_seen = {}
    left = 0
    max_len = 0

    for right in range(len(s)):
        ch = s[right]
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        max_len = max(max_len, right - left + 1)

    return max_len

Time complexity: O(n) — each character is visited once. Space complexity: O(min(n, m)) where m is the character set size (26 for lowercase English).

Problem 2: Minimum Window Substring

LeetCode 76. Given strings s and t, return the minimum window substring of s that contains all characters in t (including duplicates). If no such window exists, return "".

Approach

This is a “find the shortest valid window” problem. Expand right until the window contains all characters of t, then shrink left to minimize.

def min_window(s: str, t: str) -> str:
    from collections import Counter

    if not t or not s:
        return ""

    t_count = Counter(t)
    required = len(t_count)  # number of unique chars needed

    # formed tracks how many unique chars in current window
    # match their required frequency
    formed = 0
    window_counts = {}

    # (window length, left, right)
    ans = (float('inf'), 0, 0)
    left = 0

    for right in range(len(s)):
        ch = s[right]
        window_counts[ch] = window_counts.get(ch, 0) + 1

        # Check if frequency of ch matches the required frequency
        if ch in t_count and window_counts[ch] == t_count[ch]:
            formed += 1

        # Try to shrink the window
        while formed == required:
            # Update answer
            window_len = right - left + 1
            if window_len {'<'} ans[0]:
                ans = (window_len, left, right)

            # Remove s[left] from window
            out = s[left]
            window_counts[out] -= 1
            if out in t_count and window_counts[out] {'<'} t_count[out]:
                formed -= 1
            left += 1

    return "" if ans[0] == float('inf') else s[ans[1]:ans[2] + 1]

Walkthrough

For s = "ADOBECODEBANC", t = "ABC":

• Expand until window ADOBEC contains A, B, C. Length 6.
• Shrink left: remove A — now missing A, stop. Record length 6.
• Expand right to find next A in CODEBA. Window DOBECODEBA is not minimal yet.
• Continue shrinking. Eventually find BANC with length 4.
• Answer: "BANC".

Time complexity: O(|s| + |t|) — each character in s is visited at most twice (once by right, once by left). Space complexity: O(|s| + |t|) in the worst case for the hash maps.

Problem 3: Longest Substring with At Most K Distinct Characters

LeetCode 340. Given a string s and an integer k, find the length of the longest substring that contains at most k distinct characters.

Approach

Variable-size window. The window is invalid when the number of distinct characters exceeds k.

def longest_k_distinct(s: str, k: int) -> int:
    from collections import defaultdict

    freq = defaultdict(int)
    left = 0
    max_len = 0

    for right in range(len(s)):
        freq[s[right]] += 1

        # Shrink while too many distinct characters
        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

Example

For s = "eceba", k = 2:

• e — 1 distinct, max_len = 1.
• ec — 2 distinct, max_len = 2.
• ece — 2 distinct, max_len = 3.
• eceb — 3 distinct, shrink: remove e at index 0. ceb still has 3. Remove c. eb has 2. max_len stays 3.
• eba — 3 distinct, shrink again. Eventually max_len = 3.
• Answer: 3 ("ece").

Time complexity: O(n). Space complexity: O(k).

Problem 4: Permutation in String

LeetCode 567. Given two strings s1 and s2, return True if s2 contains a permutation of s1.

Approach

A permutation of s1 is an anagram — same characters, same frequencies. Use a fixed-size window of length len(s1) and slide it across s2. Compare frequency maps.

def check_inclusion(s1: str, s2: str) -> bool:
    from collections import Counter

    if len(s1) > len(s2):
        return False

    s1_count = Counter(s1)
    window_count = Counter(s2[:len(s1)])

    if window_count == s1_count:
        return True

    for right in range(len(s1), len(s2)):
        # Add new character on the right
        ch_in = s2[right]
        window_count[ch_in] = window_count.get(ch_in, 0) + 1

        # Remove character going out on the left
        ch_out = s2[right - len(s1)]
        window_count[ch_out] -= 1
        if window_count[ch_out] == 0:
            del window_count[ch_out]

        if window_count == s1_count:
            return True

    return False

Optimized with a match counter

Comparing two Counter objects every step is O(26) for lowercase English, which is fine. But you can optimize further by tracking how many characters have matching frequencies:

def check_inclusion_optimized(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False

    s1_count = [0] * 26
    window = [0] * 26

    for ch in s1:
        s1_count[ord(ch) - ord('a')] += 1
    for ch in s2[:len(s1)]:
        window[ord(ch) - ord('a')] += 1

    matches = sum(1 for i in range(26) if s1_count[i] == window[i])

    for right in range(len(s1), len(s2)):
        if matches == 26:
            return True

        # Add right character
        idx = ord(s2[right]) - ord('a')
        window[idx] += 1
        if window[idx] == s1_count[idx]:
            matches += 1
        elif window[idx] == s1_count[idx] + 1:
            matches -= 1

        # Remove left character
        idx = ord(s2[right - len(s1)]) - ord('a')
        window[idx] -= 1
        if window[idx] == s1_count[idx]:
            matches += 1
        elif window[idx] == s1_count[idx] - 1:
            matches -= 1

    return matches == 26

Time complexity: O(n) where n = len(s2). Space complexity: O(1) — fixed arrays of size 26.

Problem 5: Find All Anagrams in a String

LeetCode 438. Given strings s and p, return all start indices of p’s anagrams in s.

Approach

This is almost identical to the permutation problem, but instead of returning True on the first match, collect all matching positions.

def find_anagrams(s: str, p: str) -> list:
    from collections import Counter

    if len(p) > len(s):
        return []

    p_count = Counter(p)
    window = Counter(s[:len(p)])
    result = []

    if window == p_count:
        result.append(0)

    for right in range(len(p), len(s)):
        ch_in = s[right]
        window[ch_in] = window.get(ch_in, 0) + 1

        ch_out = s[right - len(p)]
        window[ch_out] -= 1
        if window[ch_out] == 0:
            del window[ch_out]

        if window == p_count:
            result.append(right - len(p) + 1)

    return result

Example

For s = "cbaebabacd", p = "abc":

• Window cba matches — add index 0.
• Slide: bae, aeb, eba, bab, aba, bac — index 6 matches.
• Slide: acd — no match.
• Answer: [0, 6].

Time complexity: O(n) where n = len(s). Comparing Counters is O(26) = O(1) for lowercase. Space complexity: O(1) — at most 26 keys.

Summary of patterns

Problem	Window Type	Invalid When	Track	Complexity
Longest without repeats	Variable	Any char freq > 1	Frequency map	O(n)
Minimum window substring	Variable	Missing required chars	Freq + match count	O(n)
At most K distinct	Variable	Distinct count > k	Frequency map size	O(n)
Permutation in string	Fixed	Frequencies mismatch	Two frequency maps	O(n)
Find all anagrams	Fixed	Frequencies mismatch	Two frequency maps	O(n)

Common mistakes

1. Off-by-one errors. The window length is right - left + 1, not right - left. Double-check when shrinking.
2. Not cleaning up zero-count entries. When a character’s frequency drops to 0, delete it from the map. Otherwise len(freq) will overcount distinct characters.
3. Forgetting to check the initial window in fixed-size problems. The first window needs to be checked before the sliding loop starts.
4. Using the wrong comparison. For “at most K distinct”, the shrink condition is len(freq) > k, not >= k.

When to use sliding window vs other techniques

• Sliding window: Contiguous substrings or subarrays with a constraint on content.
• Two pointers (non-window): Sorted arrays, palindromes, pair sums.
• Hash map alone: Non-contiguous patterns, counting across the whole string.
• Dynamic programming: Subsequences (not substrings), optimal partition problems.

Practice problems

Try these to solidify the pattern:

1. LeetCode 3 — Longest Substring Without Repeating Characters
2. LeetCode 76 — Minimum Window Substring
3. LeetCode 340 — Longest Substring with At Most K Distinct Characters
4. LeetCode 567 — Permutation in String
5. LeetCode 438 — Find All Anagrams in a String
6. LeetCode 424 — Longest Repeating Character Replacement
7. LeetCode 1004 — Max Consecutive Ones III
8. LeetCode 904 — Fruit Into Baskets
9. LeetCode 1208 — Get Equal Substrings Within Budget
10. LeetCode 30 — Substring with Concatenation of All Words

Final thoughts

The sliding window is not just a technique — it is a way of thinking. Every time you see “find a substring that satisfies X”, your first instinct should be to ask: can I maintain a window and slide it? The answer is usually yes, and the template above will get you 80% of the way there. The remaining 20% is understanding what state to track and when the window is invalid.

Master these five problems and you will recognize the pattern instantly in interviews. The template is your weapon — internalize it.