Sliding Window Algorithm Guide | String Problems | String

Overview

The sliding window technique is one of the most powerful patterns for solving string and array problems efficiently. It transforms brute-force O(n²) or O(n³) solutions into elegant O(n) linear-time algorithms by maintaining a "window" of elements and sliding it across the input.

At its core, sliding window keeps two pointers (left and right) that define a contiguous segment of the string. You expand the window by moving right to include new elements, and shrink it by moving left when the window violates a condition. This ensures each element is processed at most twice—once when added and once when removed—resulting in O(n) time complexity.

!Sliding window visualization

Fixed vs Variable Size

Sliding window problems fall into two main categories:

Fixed-Size Window

The window maintains a constant size k. You slide it one position at a time, updating your answer based on the current window.

Example: Find the maximum sum of k consecutive elements.

function maxSumOfKConsecutive(arr: number[], k: number): number {
  let windowSum = 0;
  // Initialize window sum
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  let maxSum = windowSum;
  
  // Slide the window
  for (let i = k; i < arr.length; i++) {
    windowSum = windowSum - arr[i - k] + arr[i]; // Remove left, add right
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

Time: O(n), Space: O(1)

Variable-Size Window

The window size changes dynamically based on a condition. You expand until the window becomes invalid, then shrink from the left until it's valid again. You're typically looking for the longest or shortest valid window.

Example: Longest substring without repeating characters.

function lengthOfLongestSubstring(s: string): number {
  const seen = new Set<string>();
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    // Shrink window until no duplicate
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Time: O(n), Space: O(min(n, alphabet size))

How It Works

The sliding window algorithm follows a consistent pattern:

Initialize left = 0 and right = 0 (or start with a fixed-size window)
Expand by moving right and adding s[right] to your tracking structure (set, map, or counter)
Shrink (for variable-size) by moving left and removing s[left] when the window violates the condition
Update your answer (max length, min length, count, etc.) after each valid window state
Repeat until right reaches the end

The key insight: each element enters the window once (via right) and exits at most once (via left), so total operations are O(n).

When to Use Sliding Window

Use sliding window when you see these signals:

"Longest substring" or "shortest substring" satisfying a condition
"Substring with at most K distinct characters" or "at least K"
"Minimum window substring" containing all characters of another string
"Subarray sum" problems (though arrays, same pattern)
The problem asks for a contiguous segment (substring/subarray), not a subsequence

Key distinction: If the problem asks for a subsequence (non-contiguous), sliding window usually doesn't apply—consider dynamic programming or two pointers moving in one direction instead.

Common Patterns

Pattern 1: Longest Substring Without Repeating Characters

Track characters in a Set. When a duplicate appears, shrink from left until the duplicate is removed.

Pattern 2: Minimum Window Substring

Track required characters in a Map with counts. Expand until all required characters are present, then shrink to find the minimum valid window.

function minWindow(s: string, t: string): string {
  const need = new Map<string, number>();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  
  let left = 0, right = 0;
  let valid = 0; // Count of satisfied requirements
  const window = new Map<string, number>();
  let start = 0, len = Infinity;
  
  while (right < s.length) {
    const c = s[right];
    right++;
    
    if (need.has(c)) {
      window.set(c, (window.get(c) || 0) + 1);
      if (window.get(c) === need.get(c)) valid++;
    }
    
    while (valid === need.size) {
      if (right - left < len) {
        start = left;
        len = right - left;
      }
      
      const d = s[left];
      left++;
      
      if (need.has(d)) {
        if (window.get(d) === need.get(d)) valid--;
        window.set(d, (window.get(d) || 0) - 1);
      }
    }
  }
  
  return len === Infinity ? "" : s.substring(start, start + len);
}

Pattern 3: Substring with At Most K Distinct Characters

Track character frequencies. Expand until distinct count exceeds K, then shrink.

function lengthOfLongestSubstringKDistinct(s: string, k: number): number {
  const freq = new Map<string, number>();
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    freq.set(s[right], (freq.get(s[right]) || 0) + 1);
    
    while (freq.size > k) {
      freq.set(s[left], freq.get(s[left])! - 1);
      if (freq.get(s[left]) === 0) freq.delete(s[left]);
      left++;
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Template (Variable-Size Window)

Here's a reusable template for variable-size sliding window problems:

function slidingWindowTemplate(s: string): number {
  const window = new Map(); // or Set, or array for frequency
  let left = 0;
  let result = 0; // or "", or []
  
  for (let right = 0; right < s.length; right++) {
    // Add s[right] to window
    window.set(s[right], (window.get(s[right]) || 0) + 1);
    
    // Shrink window until condition is satisfied
    while (/* window is invalid */) {
      // Remove s[left] from window
      window.set(s[left], window.get(s[left])! - 1);
      if (window.get(s[left]) === 0) window.delete(s[left]);
      left++;
    }
    
    // Update result (window is now valid)
    result = Math.max(result, right - left + 1);
  }
  
  return result;
}

Time and Space Complexity

Time: O(n) — each element is added and removed at most once
Space: O(k) where k is the size of the character set or distinct elements in the window (often O(1) for fixed alphabet like lowercase letters)

Practice Tips

Identify the condition — What makes a window valid or invalid?
Choose the tracking structure — Set for uniqueness, Map for frequencies/counts
Decide when to shrink — Usually when the condition is violated
Update answer at the right time — After ensuring the window is valid
Handle edge cases — Empty string, single character, all same characters

Related Concepts

Two Pointers — Similar technique but pointers move independently or from opposite ends
Array Sliding Window — Same pattern applies to array problems (subarray sum, etc.)
Dynamic Programming — Use DP for subsequence problems; sliding window for substrings

Mastering sliding window will help you solve a large class of string and array problems efficiently in coding interviews.