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_lenOptimization: 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 bestFind 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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the sliding window technique and when should you use it?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “A sliding window uses two pointers (left and right) to represent the boundaries of a contiguous subarray or substring. Expanding right includes new elements; shrinking left removes old ones. The key insight: instead of recomputing from scratch for each window position, update incrementally (add right, remove left). This gives O(n) solutions for problems that would otherwise need O(n^2) with nested loops. Use sliding window for: longest/shortest substring satisfying a constraint, finding all substrings matching a pattern, maximum/minimum in a window. Fixed-size window (anagrams): slide right, remove left char every step. Variable-size window (longest without repeating): expand right freely; shrink left when violated.”
}
},
{
“@type”: “Question”,
“name”: “How does the minimum window substring algorithm work?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Find the smallest window in s containing all characters of t. Use a frequency counter for t (need) and a running count of how many t-characters are currently satisfied (satisfied = count of character types whose window frequency meets the required frequency). Expand right: add s[right] to window map; if its frequency now meets need[s[right]], increment satisfied. When satisfied == len(need): all required characters are present. Shrink left: increment need[s[left]], decrement window map; if a character drops below required, decrement satisfied. Track the minimum window each time satisfied is reached. O(n) time — right pointer moves n times right; left pointer moves at most n times right total.”
}
},
{
“@type”: “Question”,
“name”: “How do you find all anagrams of p in s efficiently?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Use a fixed window of size len(p) and a difference array diff[26]. Initialize diff with frequencies of p (positive values mean p has more). Slide the window over s: for each new character s[right], decrement diff[s[right]] — if diff becomes 0, one previously positive position becomes 0 (increment match count). For removed character s[left], increment diff[s[left]] — if diff becomes 1, one position went from 0 to positive (decrement match count). When match count == 26 (all zero), the window is an anagram of p — record left index. O(n) time, O(1) space. The match count tracks how many characters currently have the exact right frequency, avoiding a full diff[] scan on each slide.”
}
},
{
“@type”: “Question”,
“name”: “What is the longest repeating character replacement algorithm?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Find the longest substring where you can replace at most k characters to make all characters the same. Key insight: the optimal strategy is always to keep the most frequent character and replace the rest. Window validity: window_length – max_freq_in_window last_seen_index. When s[right] is already in the window (last_seen[s[right]] >= left): jump left directly to last_seen[s[right]] + 1, skipping all intermediate characters. Update last_seen[s[right]] = right. Window size = right – left + 1. This is O(n) time with O(min(n, charset_size)) space. The map stores only the most recent index of each character — older occurrences outside the window are irrelevant since left has already passed them.”
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Coinbase Interview Guide