Advanced Sliding Window Patterns
Level 2.5: Interview Patterns - Master pattern recognition for variable-size windows and complex constraints
Advanced Sliding Window Pattern Recognition
🧭 When to Use This Pattern - Checklist
Pattern Recognition Checklist
✅ Use Advanced Sliding Window When:
- 🎯 Contiguous Elements Required: Problem asks for subarray/substring (not subsequence)
- 📊 Condition-Based Window Size: Window expands/contracts based on some condition
- 🔄 Frequency Constraints: "At most K distinct", "contains all characters", "permutation"
- 📈 Optimization Goal: "Longest/shortest subarray satisfying condition"
- ⚡ Linear Time Possible: Each element can be processed in amortized O(1) time
❌ Don't Use Sliding Window When:
- 🚫 Non-contiguous Elements: Subsequence problems, picking elements with gaps
- 🚫 Global Dependencies: Solution depends on entire array knowledge
- 🚫 Complex State Transitions: DP with overlapping subproblems
- 🚫 Structural Relationships: Tree/graph traversal, parent-child dependencies
🔍 Decision Flowchart:
┌─────────────────────────────────┐
│ Problem Analysis Start │
└─────────────┬───────────────────┘
│
┌─────────────▼───────────────────┐
│ Does problem involve finding │
│ subarray/substring with │
│ specific condition? │
└─────────────┬───────────────────┘
│ YES
┌─────────────▼───────────────────┐
│ Is the window size variable │
│ based on condition? │
└─────────────┬───────────────────┘
│ YES
┌─────────────▼───────────────────┐
│ Choose Pattern Type: │
│ │
│ 📊 VARIABLE SIZE WINDOW: │
│ ✓ Two pointers (left,right)│
│ ✓ Expand right, shrink left│
│ ✓ Track condition validity │
│ │
│ 🔄 FIXED SIZE + SLIDING: │
│ ✓ HashMap for frequency │
│ ✓ Slide and update counts │
│ ✓ Check condition each step│
│ │
│ 🎯 MULTIPLE POINTERS: │
│ ✓ 3+ pointers for complex │
│ ✓ Each pointer has purpose │
│ ✓ Coordinate movements │
└─────────────────────────────────┘
Variable Size Windows
Core Pattern: Expand-Contract Strategy
Variable size sliding window adapts its length based on problem constraints. The key is knowing when to expand (move right pointer) and when to contract (move left pointer).
🌍 Real-World Applications:
📱 App Analytics: Finding time periods with at most K distinct user actions
📊 Financial Trading: Longest period with total trades ≤ budget
🌐 Network Traffic: Time windows with distinct IP addresses ≤ threshold
🎮 Gaming: Longest streak with score changes ≤ variance limit
TypeScript
// Template for Variable Size Sliding Window
function variableSizeWindowTemplate<T>(
arr: T[],
isValidWindow: (windowData: any) => boolean,
updateWindowData: (data: any, element: T, isAdding: boolean) => void
): number {
let left = 0;
let maxLength = 0;
let windowData: any = {}; // Track window state
for (let right = 0; right < arr.length; right++) {
// Expand window: add arr[right]
updateWindowData(windowData, arr[right], true);
// Contract window if invalid
while (!isValidWindow(windowData)) {
updateWindowData(windowData, arr[left], false);
left++;
}
// Update result
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
// 1. Longest Substring with At Most K Distinct Characters
function lengthOfLongestSubstringKDistinct(s: string, k: number): number {
if (k === 0) return 0;
const charCount = new Map<string, number>();
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
// Expand: add character
const rightChar = s[right];
charCount.set(rightChar, (charCount.get(rightChar) || 0) + 1);
// Contract: remove characters to maintain at most k distinct
while (charCount.size > k) {
const leftChar = s[left];
const count = charCount.get(leftChar)! - 1;
if (count === 0) {
charCount.delete(leftChar);
} else {
charCount.set(leftChar, count);
}
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
// 2. Longest Substring Without Repeating Characters
function lengthOfLongestSubstring(s: string): number {
const charSet = new Set<string>();
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
// Contract: remove duplicates
while (charSet.has(s[right])) {
charSet.delete(s[left]);
left++;
}
// Expand: add current character
charSet.add(s[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
// 3. Minimum Window with Sum >= Target
function minSubArrayLen(target: number, nums: number[]): number {
let left = 0;
let sum = 0;
let minLength = Infinity;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
// Contract window while sum >= target
while (sum >= target) {
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLength === Infinity ? 0 : minLength;
}
// Example usage
function demonstrateVariableWindow(): void {
console.log("At Most K Distinct Characters:");
console.log(lengthOfLongestSubstringKDistinct("eceba", 2)); // 3 ("ece")
console.log("\nLongest Substring Without Repeating:");
console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
console.log("\nMinimum Window Sum:");
console.log(minSubArrayLen(7, [2,3,1,2,4,3])); // 2
}
Python
# Variable Size Sliding Window Template
def variable_size_window_template(arr, is_valid_window, update_window_data):
"""Generic template for variable size sliding window problems"""
left = 0
max_length = 0
window_data = {} # Track window state
for right in range(len(arr)):
# Expand window: add arr[right]
update_window_data(window_data, arr[right], True)
# Contract window if invalid
while not is_valid_window(window_data):
update_window_data(window_data, arr[left], False)
left += 1
# Update result
max_length = max(max_length, right - left + 1)
return max_length
# 1. Longest Substring with At Most K Distinct Characters
def length_of_longest_substring_k_distinct(s, k):
"""Find longest substring with at most k distinct characters"""
if k == 0:
return 0
from collections import defaultdict
char_count = defaultdict(int)
left = 0
max_length = 0
for right, char in enumerate(s):
# Expand: add character
char_count[char] += 1
# Contract: maintain at most k distinct
while len(char_count) > k:
left_char = s[left]
char_count[left_char] -= 1
if char_count[left_char] == 0:
del char_count[left_char]
left += 1
max_length = max(max_length, right - left + 1)
return max_length
# 2. Longest Substring Without Repeating Characters
def length_of_longest_substring(s):
"""Find longest substring without repeating characters"""
char_set = set()
left = 0
max_length = 0
for right, char in enumerate(s):
# Contract: remove duplicates
while char in char_set:
char_set.remove(s[left])
left += 1
# Expand: add current character
char_set.add(char)
max_length = max(max_length, right - left + 1)
return max_length
# 3. Minimum Window with Sum >= Target
def min_sub_array_len(target, nums):
"""Find minimum length subarray with sum >= target"""
left = 0
current_sum = 0
min_length = float('inf')
for right in range(len(nums)):
current_sum += nums[right]
# Contract window while sum >= target
while current_sum >= target:
min_length = min(min_length, right - left + 1)
current_sum -= nums[left]
left += 1
return 0 if min_length == float('inf') else min_length
# Example usage
def demonstrate_variable_window():
print("At Most K Distinct Characters:")
print(length_of_longest_substring_k_distinct("eceba", 2)) # 3
print("\nLongest Substring Without Repeating:")
print(length_of_longest_substring("abcabcbb")) # 3
print("\nMinimum Window Sum:")
print(min_sub_array_len(7, [2, 3, 1, 2, 4, 3])) # 2
OCaml
open Printf
(* 1. Longest Substring with At Most K Distinct Characters *)
let length_of_longest_substring_k_distinct s k =
if k = 0 then 0
else
let char_count = Hashtbl.create 26 in
let left = ref 0 in
let max_length = ref 0 in
let n = String.length s in
for right = 0 to n - 1 do
let char = s.[right] in
(* Expand: add character *)
let current_count = try Hashtbl.find char_count char with Not_found -> 0 in
Hashtbl.replace char_count char (current_count + 1);
(* Contract: maintain at most k distinct *)
while Hashtbl.length char_count > k do
let left_char = s.[!left] in
let count = Hashtbl.find char_count left_char in
if count = 1 then
Hashtbl.remove char_count left_char
else
Hashtbl.replace char_count left_char (count - 1);
incr left
done;
max_length := max !max_length (right - !left + 1)
done;
!max_length
(* 2. Longest Substring Without Repeating Characters *)
let length_of_longest_substring s =
let char_set = Hashtbl.create 26 in
let left = ref 0 in
let max_length = ref 0 in
let n = String.length s in
for right = 0 to n - 1 do
let char = s.[right] in
(* Contract: remove duplicates *)
while Hashtbl.mem char_set char do
Hashtbl.remove char_set s.[!left];
incr left
done;
(* Expand: add current character *)
Hashtbl.add char_set char true;
max_length := max !max_length (right - !left + 1)
done;
!max_length
(* Example usage *)
let demonstrate_variable_window () =
printf "At Most K Distinct Characters: %d\n"
(length_of_longest_substring_k_distinct "eceba" 2);
printf "Longest Substring Without Repeating: %d\n"
(length_of_longest_substring "abcabcbb")
| Problem Type | Time Complexity | Space Complexity | Key Insight |
|---|---|---|---|
| Variable Size Window | O(n) | O(k) where k is distinct elements | Each element added/removed once |
| Unique Characters | O(n) | O(min(m, n)) where m is charset size | Set operations for duplicates |
| At Most K Constraint | O(n) | O(k) | Contract when constraint violated |
String Permutation Problems
Fixed Size Window with Frequency Matching
String permutation problems typically involve finding anagrams or character rearrangements within a string. These use fixed-size sliding windows combined with frequency counting to efficiently detect permutations.
🌍 Real-World Applications:
🔐 Cryptography: Finding anagram-based cipher patterns in encrypted text
🧬 Bioinformatics: DNA sequence analysis for gene variants and mutations
📝 Text Analysis: Plagiarism detection through character frequency matching
🎯 Search Engines: Query matching with character permutation tolerance
TypeScript
// 1. Find All Anagrams in String
function findAnagrams(s: string, p: string): number[] {
if (p.length > s.length) return [];
const result: number[] = [];
const pCount = new Map<string, number>();
const windowCount = new Map<string, number>();
// Count characters in pattern
for (const char of p) {
pCount.set(char, (pCount.get(char) || 0) + 1);
}
// Initialize window
for (let i = 0; i < p.length; i++) {
const char = s[i];
windowCount.set(char, (windowCount.get(char) || 0) + 1);
}
// Check if initial window is anagram
if (mapsEqual(pCount, windowCount)) {
result.push(0);
}
// Slide window
for (let i = p.length; i < s.length; i++) {
// Add new character
const newChar = s[i];
windowCount.set(newChar, (windowCount.get(newChar) || 0) + 1);
// Remove old character
const oldChar = s[i - p.length];
const oldCount = windowCount.get(oldChar)! - 1;
if (oldCount === 0) {
windowCount.delete(oldChar);
} else {
windowCount.set(oldChar, oldCount);
}
// Check if current window is anagram
if (mapsEqual(pCount, windowCount)) {
result.push(i - p.length + 1);
}
}
return result;
}
function mapsEqual(map1: Map<string, number>, map2: Map<string, number>): boolean {
if (map1.size !== map2.size) return false;
for (const [key, value] of map1) {
if (map2.get(key) !== value) return false;
}
return true;
}
// 2. Permutation in String
function checkInclusion(s1: string, s2: string): boolean {
if (s1.length > s2.length) return false;
const s1Count = new Map<string, number>();
const windowCount = new Map<string, number>();
// Count characters in s1
for (const char of s1) {
s1Count.set(char, (s1Count.get(char) || 0) + 1);
}
let left = 0;
let matches = 0;
for (let right = 0; right < s2.length; right++) {
const rightChar = s2[right];
// Expand window
if (s1Count.has(rightChar)) {
windowCount.set(rightChar, (windowCount.get(rightChar) || 0) + 1);
if (windowCount.get(rightChar) === s1Count.get(rightChar)) {
matches++;
}
}
// Contract window if too large
if (right - left + 1 > s1.length) {
const leftChar = s2[left];
if (s1Count.has(leftChar)) {
if (windowCount.get(leftChar) === s1Count.get(leftChar)) {
matches--;
}
const leftCount = windowCount.get(leftChar)! - 1;
if (leftCount === 0) {
windowCount.delete(leftChar);
} else {
windowCount.set(leftChar, leftCount);
}
}
left++;
}
// Check if we have a match
if (matches === s1Count.size) return true;
}
return false;
}
// 3. Minimum Window Substring
function minWindow(s: string, t: string): string {
if (t.length > s.length) return "";
const tCount = new Map<string, number>();
for (const char of t) {
tCount.set(char, (tCount.get(char) || 0) + 1);
}
let left = 0;
let minLength = Infinity;
let minStart = 0;
let formed = 0;
const required = tCount.size;
const windowCount = new Map<string, number>();
for (let right = 0; right < s.length; right++) {
const rightChar = s[right];
// Expand window
windowCount.set(rightChar, (windowCount.get(rightChar) || 0) + 1);
if (tCount.has(rightChar) && windowCount.get(rightChar) === tCount.get(rightChar)) {
formed++;
}
// Contract window
while (formed === required && left <= right) {
// Update minimum if current window is smaller
if (right - left + 1 < minLength) {
minLength = right - left + 1;
minStart = left;
}
const leftChar = s[left];
windowCount.set(leftChar, windowCount.get(leftChar)! - 1);
if (tCount.has(leftChar) && windowCount.get(leftChar)! < tCount.get(leftChar)!) {
formed--;
}
left++;
}
}
return minLength === Infinity ? "" : s.substring(minStart, minStart + minLength);
}
// Example usage
function demonstrateStringPermutations(): void {
console.log("Find Anagrams:");
console.log(findAnagrams("cbaebabacd", "abc")); // [1, 6]
console.log("\nPermutation in String:");
console.log(checkInclusion("ab", "eidbaooo")); // true
console.log("\nMinimum Window Substring:");
console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"
}
Python
# String Permutation Problems
# 1. Find All Anagrams in String
def find_anagrams(s, p):
"""Find all start indices of p's anagrams in s"""
if len(p) > len(s):
return []
from collections import Counter
result = []
p_count = Counter(p)
window_count = Counter()
# Initialize window
for i in range(len(p)):
window_count[s[i]] += 1
# Check if initial window is anagram
if window_count == p_count:
result.append(0)
# Slide window
for i in range(len(p), len(s)):
# Add new character
window_count[s[i]] += 1
# Remove old character
old_char = s[i - len(p)]
window_count[old_char] -= 1
if window_count[old_char] == 0:
del window_count[old_char]
# Check if current window is anagram
if window_count == p_count:
result.append(i - len(p) + 1)
return result
# 2. Permutation in String
def check_inclusion(s1, s2):
"""Check if s2 contains permutation of s1"""
if len(s1) > len(s2):
return False
from collections import Counter
s1_count = Counter(s1)
window_count = Counter()
left = 0
matches = 0
for right in range(len(s2)):
right_char = s2[right]
# Expand window
if right_char in s1_count:
window_count[right_char] += 1
if window_count[right_char] == s1_count[right_char]:
matches += 1
# Contract window if too large
if right - left + 1 > len(s1):
left_char = s2[left]
if left_char in s1_count:
if window_count[left_char] == s1_count[left_char]:
matches -= 1
window_count[left_char] -= 1
if window_count[left_char] == 0:
del window_count[left_char]
left += 1
# Check if we have a match
if matches == len(s1_count):
return True
return False
# 3. Minimum Window Substring
def min_window(s, t):
"""Find minimum window substring containing all characters of t"""
if len(t) > len(s):
return ""
from collections import Counter, defaultdict
t_count = Counter(t)
window_count = defaultdict(int)
left = 0
min_length = float('inf')
min_start = 0
formed = 0
required = len(t_count)
for right in range(len(s)):
right_char = s[right]
# Expand window
window_count[right_char] += 1
if right_char in t_count and window_count[right_char] == t_count[right_char]:
formed += 1
# Contract window
while formed == required and left <= right:
# Update minimum if current window is smaller
if right - left + 1 < min_length:
min_length = right - left + 1
min_start = left
left_char = s[left]
window_count[left_char] -= 1
if left_char in t_count and window_count[left_char] < t_count[left_char]:
formed -= 1
left += 1
return "" if min_length == float('inf') else s[min_start:min_start + min_length]
# Example usage
def demonstrate_string_permutations():
print("Find Anagrams:")
print(find_anagrams("cbaebabacd", "abc")) # [1, 6]
print("\nPermutation in String:")
print(check_inclusion("ab", "eidbaooo")) # True
print("\nMinimum Window Substring:")
print(min_window("ADOBECODEBANC", "ABC")) # "BANC"
OCaml
open Printf
(* String Permutation Problems *)
(* 1. Find All Anagrams in String *)
let find_anagrams s p =
let s_len = String.length s in
let p_len = String.length p in
if p_len > s_len then []
else
let p_count = Hashtbl.create 26 in
let window_count = Hashtbl.create 26 in
let result = ref [] in
(* Count characters in pattern *)
for i = 0 to p_len - 1 do
let char = p.[i] in
let count = try Hashtbl.find p_count char with Not_found -> 0 in
Hashtbl.replace p_count char (count + 1)
done;
(* Initialize window *)
for i = 0 to p_len - 1 do
let char = s.[i] in
let count = try Hashtbl.find window_count char with Not_found -> 0 in
Hashtbl.replace window_count char (count + 1)
done;
(* Check if initial window is anagram *)
let maps_equal map1 map2 =
let keys1 = Hashtbl.fold (fun k _ acc -> k :: acc) map1 [] in
let keys2 = Hashtbl.fold (fun k _ acc -> k :: acc) map2 [] in
List.length keys1 = List.length keys2 &&
List.for_all (fun k ->
try Hashtbl.find map1 k = Hashtbl.find map2 k
with Not_found -> false
) keys1
in
if maps_equal p_count window_count then
result := 0 :: !result;
(* Slide window *)
for i = p_len to s_len - 1 do
(* Add new character *)
let new_char = s.[i] in
let new_count = try Hashtbl.find window_count new_char with Not_found -> 0 in
Hashtbl.replace window_count new_char (new_count + 1);
(* Remove old character *)
let old_char = s.[i - p_len] in
let old_count = Hashtbl.find window_count old_char in
if old_count = 1 then
Hashtbl.remove window_count old_char
else
Hashtbl.replace window_count old_char (old_count - 1);
(* Check if current window is anagram *)
if maps_equal p_count window_count then
result := (i - p_len + 1) :: !result
done;
List.rev !result
(* 2. Permutation in String *)
let check_inclusion s1 s2 =
let s1_len = String.length s1 in
let s2_len = String.length s2 in
if s1_len > s2_len then false
else
let s1_count = Hashtbl.create 26 in
let window_count = Hashtbl.create 26 in
let left = ref 0 in
let matches = ref 0 in
(* Count characters in s1 *)
for i = 0 to s1_len - 1 do
let char = s1.[i] in
let count = try Hashtbl.find s1_count char with Not_found -> 0 in
Hashtbl.replace s1_count char (count + 1)
done;
let required = Hashtbl.length s1_count in
let found = ref false in
for right = 0 to s2_len - 1 do
if not !found then begin
let right_char = s2.[right] in
(* Expand window *)
if Hashtbl.mem s1_count right_char then begin
let count = try Hashtbl.find window_count right_char with Not_found -> 0 in
Hashtbl.replace window_count right_char (count + 1);
if Hashtbl.find window_count right_char = Hashtbl.find s1_count right_char then
incr matches
end;
(* Contract window if too large *)
if right - !left + 1 > s1_len then begin
let left_char = s2.[!left] in
if Hashtbl.mem s1_count left_char then begin
if Hashtbl.find window_count left_char = Hashtbl.find s1_count left_char then
decr matches;
let count = Hashtbl.find window_count left_char in
if count = 1 then
Hashtbl.remove window_count left_char
else
Hashtbl.replace window_count left_char (count - 1)
end;
incr left
end;
(* Check if we have a match *)
if !matches = required then
found := true
end
done;
!found
(* Example usage *)
let demonstrate_string_permutations () =
printf "Find Anagrams: ";
let anagrams = find_anagrams "cbaebabacd" "abc" in
List.iter (printf "%d ") anagrams;
print_newline ();
printf "Permutation in String: %b\n"
(check_inclusion "ab" "eidbaooo")
| Problem Type | Time Complexity | Space Complexity | Key Insight |
|---|---|---|---|
| Find Anagrams | O(n) | O(k) where k is pattern length | Fixed window size with frequency tracking |
| Permutation Check | O(n) | O(k) | Matches counter optimization |
| Minimum Window | O(n + m) | O(m) where m is target length | Variable window with condition tracking |
🎯 Interview Tips & Common Patterns
Interview Strategy Guide
🔍 Pattern Recognition in Interviews:
- Keywords to Watch: "subarray", "substring", "contiguous", "window", "at most", "exactly", "permutation"
- Question Clarification: Ask about character sets, case sensitivity, empty inputs
- Edge Cases: Empty strings, single character, pattern longer than string
- Optimization Path: Start with brute force, then optimize to sliding window
💡 Implementation Tips:
- Use Maps for Frequency: HashMap/Counter for character counting
- Two Pointer Technique: left and right pointers, expand right first
- Condition Checking: Maintain valid window state efficiently
- Result Tracking: Update result when window is valid
⚠️ Common Mistakes to Avoid:
- Off-by-one Errors: Carefully handle window boundaries
- Map Operations: Check if key exists before accessing
- Window Size: Don't forget to handle fixed vs variable size
- State Management: Keep window state consistent during expansion/contraction
🌟 Interview Success Framework:
📋 Step 1 - Understand: Clarify problem constraints and requirements
🎯 Step 2 - Identify: Recognize sliding window pattern from keywords
⚙️ Step 3 - Design: Choose variable/fixed size and data structures
💻 Step 4 - Implement: Code with proper edge case handling
🧪 Step 5 - Test: Verify with examples and edge cases