String Sliding Window Interview Patterns: Longest Substring, Anagram, Minimum Window (2025)

By /
⏱ 5 min read

The Sliding Window Technique for Strings

A sliding window maintains a contiguous substring without re-scanning from scratch. Two pointers (left and right) define the window boundaries. Expand right to include new characters; shrink left when the window violates a constraint. O(n) time because each character is added and removed at most once.

Longest Substring Without Repeating Characters (LC 3)

Maintain a set of characters in the current window. Expand right. If right char is already in the set: shrink left until the duplicate is removed. Track max window size.

def length_of_longest_substring(s: str) -> int:
    seen = set()
    left = max_len = 0
    for right, ch in enumerate(s):
        while ch in seen:
            seen.remove(s[left]); left += 1
        seen.add(ch)
        max_len = max(max_len, right - left + 1)
    return max_len

Optimization: use a hashmap of char->last_index. Jump left directly to last_index[ch]+1 instead of shrinking one by one. O(n) with O(1) shrink per step.

Minimum Window Substring (LC 76)

Find the smallest window in s containing all characters of t. Use a frequency map for t. Maintain a window frequency map and a count of how many required characters are satisfied (have sufficient frequency). Expand right: add char to window map; if its count meets the required count, increment satisfied. When satisfied == len(required): try to shrink left while still satisfied. Record minimum window on each shrink step.

from collections import Counter

def min_window(s: str, t: str) -> str:
    need = Counter(t)
    missing = len(t)
    best = ""
    left = 0
    for right, ch in enumerate(s):
        if need[ch] > 0: missing -= 1
        need[ch] -= 1
        if missing == 0:
            while need[s[left]] < 0:
                need[s[left]] += 1; left += 1
            if not best or right - left + 1 < len(best):
                best = s[left:right+1]
            need[s[left]] += 1; missing += 1; left += 1
    return best

Find All Anagrams in a String (LC 438)

Anagram = same character frequencies. Fixed-size window of len(p). Use a frequency array diff[26] = freq(p) – freq(window). Count non-zero positions. When count == 0: window is an anagram. On slide: remove leftmost char (decrement diff, update count). Add new rightmost char (decrement diff, update count). O(n) time, O(1) space (fixed 26-char array).

Longest Repeating Character Replacement (LC 424)

Find the longest substring where replacing at most k characters makes all chars the same. Key insight: the window is valid if window_length – max_freq_in_window <= k (at most k replacements needed). Expand right; update max_freq. If window becomes invalid: shrink left by 1 (do not update max_freq — we only care if we can do better). O(n), O(26).

Permutation in String (LC 567)

Check if any permutation of s1 appears in s2. Fixed window of size len(s1). Same approach as Find All Anagrams: count non-zero positions in diff[]. If 0, a permutation exists. O(n) where n = len(s2).

Template: Variable vs Fixed Window

Fixed window (anagram, permutation): window size = len(pattern). Slide right, remove left char on each step. Variable window (longest without repeating, minimum window): right expands freely; left shrinks when constraint violated. The key insight: shrink from left to restore validity; expand right to search for a better answer.

Asked at: Meta Interview Guide

Asked at: Apple Interview Guide

Asked at: LinkedIn Interview Guide

Asked at: Coinbase Interview Guide

Scroll to Top