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

Source: https://www.techinterview.org/post/3233464822/string-sliding-window-interview-patterns/
Updated: 2026-05-02 · techinterview.org

## 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](https://www.techinterview.org/post/3233476081/sliding-window-longest-substring-without-repeats/) 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](https://techinterview.org/meta-interview/)

Asked at: [Apple Interview Guide](https://techinterview.org/apple-interview/)

Asked at: [LinkedIn Interview Guide](https://techinterview.org/linkedin-interview/)

Asked at: [Coinbase Interview Guide](https://techinterview.org/coinbase-interview/)