Sliding Window Technique

The Sliding Window pattern is used to perform a required operation on a specific window size of a given array or string, such as finding the longest substring containing all 1s. Sliding Windows start from the 1st element and keep shifting right by one element and adjust the length of the window according to the problem that you are solving.

In many cases, this technique converts a nested loop operation (O(N²)) into a single loop operation (O(N)).

1. Types of Sliding Windows

There are two primary types of sliding windows:

1. Fixed Size Window: The window size is fixed (e.g., “find the maximum sum of any subarray of size k”).
2. Dynamic Size Window: The window grows or shrinks based on constraints (e.g., “find the smallest subarray with a sum greater than s”).

---

2. The Mathematical Anchor: Loop Invariants

To prove a sliding window algorithm is correct, we use a Loop Invariant. This is a property that must be true at the beginning of every iteration.

The Invariant Blueprint

“For any window defined by [left, right], the state (e.g., current<sub>sum</sub>, frequency<sub>map</sub>) accurately reflects the elements within that boundary, and the constraint is satisfied locally.”

Example: Longest Substring Without Repeating Characters

• Initialization: left = 0, right = 0. Window is empty or has 1 char. Invariant holds.
• Maintenance: If we add arr[right] and it’s a duplicate, we increment left until the duplicate is gone. After this adjust, the window [left, right] once again contains only unique characters.
• Termination: When right reaches the end, we have checked every possible valid window starting position, and the max<sub>length</sub> tracks the global optimum.

---

3. Interactive Visualizer: Dynamic Sliding Window

The following visualizer demonstrates finding the Longest Substring Without Repeating Characters. Watch how the left and right pointers move. The window expands (right moves) as long as characters are unique. When a duplicate is found, the window shrinks (left moves) until the duplicate is removed.

Speed:

Press Start to begin...

Current Window: ""

Max Length: 0

4. Problem 1: Longest Substring Without Repeating Characters

Difficulty: Medium

Given a string s, find the length of the longest substring without duplicate characters.

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Solution Walkthrough

We can use the Sliding Window technique with a HashSet (or a boolean array/map) to keep track of characters in the current window.

1. Initialize left = 0, right = 0, maxLen = 0.
2. Iterate right from 0 to end.
3. If s[right] is in the set, it means we have a duplicate. Increment left and remove s[left] from the set until s[right] is no longer in the set.
4. Add s[right] to the set.
5. Update maxLen = max(maxLen, right - left + 1).

View Java Solution

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

class Solution {
  public int lengthOfLongestSubstring(String s) {
    Set<Character> chars = new HashSet<>();
    int left = 0;
    int maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
      char c = s.charAt(right);

      // If duplicate found, shrink window from left
      while (chars.contains(c)) {
        chars.remove(s.charAt(left));
        left++;
      }

      chars.add(c);
      maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
  }
}

View Go Solution

package main

func lengthOfLongestSubstring(s string) int {
	chars := make(map[byte]bool)
	left := 0
	maxLen := 0

	for right := 0; right < len(s); right++ {
		c := s[right]

		// If duplicate found, shrink window from left
		for chars[c] {
			delete(chars, s[left])
			left++
		}

		chars[c] = true

		currentLen := right - left + 1
		if currentLen > maxLen {
			maxLen = currentLen
		}
	}

	return maxLen
}

---

5. Problem 2: Minimum Window Substring

Difficulty: Hard

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

Example:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Solution Walkthrough

This problem requires a dynamic sliding window with frequency counting.

1. Count the frequency of characters in t.
2. Expand right pointer to include characters from s.
3. When the window contains all characters from t (valid window), try to shrink it from the left to make it minimal.
4. Keep track of the minimum window size and starting position found so far.

View Java Solution

import java.util.HashMap;
import java.util.Map;

class Solution {
  public String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";

    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) {
      need.put(c, need.getOrDefault(c, 0) + 1);
    }

    int left = 0, right = 0;
    int required = need.size(); // Number of unique characters needed
    int formed = 0; // Number of unique characters satisfying the count

    Map<Character, Integer> window = new HashMap<>();
    int[] ans = {-1, 0, 0}; // length, left, right

    while (right < s.length()) {
      char c = s.charAt(right);
      window.put(c, window.getOrDefault(c, 0) + 1);

      if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {
        formed++;
      }

      // Try to contract the window
      while (left <= right && formed == required) {
        c = s.charAt(left);

        // Save smallest window
        if (ans[0] == -1 || right - left + 1 < ans[0]) {
          ans[0] = right - left + 1;
          ans[1] = left;
          ans[2] = right;
        }

        // Remove from left
        window.put(c, window.get(c) - 1);
        if (need.containsKey(c) && window.get(c).intValue() < need.get(c).intValue()) {
          formed--;
        }
        left++;
      }
      right++;
    }

    return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
  }
}

View Go Solution

package main

import "math"

func minWindow(s string, t string) string {
	if len(s) == 0 || len(t) == 0 {
		return ""
	}

	need := make(map[byte]int)
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}

	required := len(need)
	formed := 0
	window := make(map[byte]int)

	l, r := 0, 0
	ans := []int{-1, 0, 0} // length, left, right

	for r < len(s) {
		c := s[r]
		window[c]++

		if count, ok := need[c]; ok && window[c] == count {
			formed++
		}

		for l <= r && formed == required {
			c = s[l]

			if ans[0] == -1 || r-l+1 < ans[0] {
				ans[0] = r - l + 1
				ans[1] = l
				ans[2] = r
			}

			window[c]--
			if count, ok := need[c]; ok && window[c] < count {
				formed--
			}
			l++
		}
		r++
	}

	if ans[0] == -1 {
		return ""
	}
	return s[ans[1] : ans[2]+1]
}

---

6. Deep Dive Strategy Lab: Sliding Window Technique

Intuition Through Analogy

Think of this chapter like organizing items on a warehouse shelf. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?