Sliding Window on String

Minimum Window Substring

Find the smallest window in string S that contains all characters of string T. Expand right until all chars are included, then shrink left to minimize. Track the shortest valid window.

O(n)

How It Works

Minimum Window Substring asks for the smallest window of S containing every character of T with multiplicity. Keep a frequency map of what T still needs and a counter of how many required characters are currently satisfied. Expand the right edge, decrementing needs; once every requirement is met, shrink from the left as far as possible while the window stays valid, recording the best length before each shrink breaks validity.

This expand-then-contract rhythm visits each character at most twice, so the algorithm runs in O(|S| + |T|). Brute force would examine O(n²) windows and re-count each one; the incremental frequency map is what removes that redundant recounting.

Step-by-Step Visualization

Find min window in S containing all of T='ABC'

NeedA:1, B:1, C:1

1/4

Code

Java

static String minWindow(String s, String t) {
  Map<Character, Integer> need = new HashMap<>();
  for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
  int have = 0, required = need.size();
  int left = 0, minLen = Integer.MAX_VALUE;
  String result = "";

  for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    if (need.containsKey(c)) {
      need.put(c, need.get(c) - 1);
      if (need.get(c) == 0) have++;
    }
    while (have == required) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        result = s.substring(left, right + 1);
      }
      char lc = s.charAt(left);
      if (need.containsKey(lc)) {
        need.put(lc, need.get(lc) + 1);
        if (need.get(lc) > 0) have--;
      }
      left++;
    }
  }
  return result;
}

Tips & Gotchas

1Expand right to find a valid window, then shrink left to minimize

2Use a frequency map to track how many chars still needed

3A counter tracks how many unique chars are fully satisfied

Practice Problems

1Minimum Window Substring
2Minimum Size Subarray Sum
3Substring with Concatenation of All Words
4Minimum Window Subsequence

About the Sliding Window on String Pattern

Apply the sliding window technique to strings. Use a frequency map inside the window to track character counts. Expand or shrink the window based on whether the current set of characters satisfies the problem's condition.

Key insight

Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).

Common String Interview Problems

Longest Substring Without Repeating Characters
Valid Anagram
Longest Palindromic Substring
Minimum Window Substring
Group Anagrams

Frequently Asked Questions

How do I know when the window contains all of T without rescanning it?

Keep a single 'formed' counter of distinct characters whose required count is fully met. Update it in O(1) whenever a character's window count crosses its required count, and the window is valid exactly when formed equals the number of distinct characters in T.

Does this pattern handle duplicate characters in T?

Yes, as long as you track counts rather than mere presence. If T contains two a's, the window is only valid once it holds at least two a's, which the frequency map captures naturally while a set would not.