22. Minimum Window Substring

HardString Hash Table Sliding Window

Given two strings s and t, return the shortest substring of s that contains every character of t, including repeats: if t has a letter twice, the window must contain it at least twice. Letters are case-sensitive.

If no such substring exists, return the empty string "". The tests guarantee that whenever a window exists, the shortest one is unique.

Example 1

Input: s = "XAYBZCAB", t = "ABC"
Output: "CAB"

Explanation: "AYBZC" and "BZCA" also contain A, B and C, but "CAB" is the shortest.

Example 2

Input: s = "a", t = "a"
Output: "a"

Example 3

Input: s = "a", t = "aa"
Output: ""

Explanation: t needs two as but s has only one.

Constraints

1 <= s.length, t.length <= 10^5
s and t consist of uppercase and lowercase English letters

Follow-up: Can you find the answer in O(|s| + |t|) time?

💡 Hint 1

Count what t needs. A window of s is valid when it has at least that many of every character.

💡 Hint 2

Grow a window to the right until it is valid, then shrink it from the left for as long as it stays valid, recording the shortest valid window.

💡 Hint 3

Track a single number, how many required characters are still missing, so validity is an O(1) check instead of comparing all counts.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Use a sliding window with a table need of how many more of each character the window requires, and a counter missing of required characters not yet covered (initially t.length). Move right across s: if need[c] > 0 the new character fills a gap, so decrement missing; decrement need[c] either way (it goes negative for surplus). Whenever missing == 0 the window is valid: record it if it is the shortest so far, then remove s[left] (increment its need; if that becomes positive a required character is now missing) and advance left. Each index enters and leaves the window once.

Time O(|s| + |t|)Space O(1) (a fixed-size table of 128 counters)

function minWindow(s, t) {
  const need = new Array(128).fill(0);
  for (let i = 0; i < t.length; i++) need[t.charCodeAt(i)]++;
  let missing = t.length;
  let bestStart = 0;
  let bestLen = Infinity;
  let left = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s.charCodeAt(right);
    if (need[c] > 0) missing--;
    need[c]--;
    while (missing === 0) {
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestStart = left;
      }
      const d = s.charCodeAt(left);
      need[d]++;
      if (need[d] > 0) missing++;
      left++;
    }
  }
  return bestLen === Infinity ? '' : s.slice(bestStart, bestStart + bestLen);
}

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        for (int i = 0; i < t.length(); i++) need[t.charAt(i)]++;
        int missing = t.length(), bestStart = 0, bestLen = Integer.MAX_VALUE, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (need[c] > 0) missing--;
            need[c]--;
            while (missing == 0) {
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestStart = left;
                }
                char d = s.charAt(left);
                need[d]++;
                if (need[d] > 0) missing++;
                left++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
    }
}

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
function minWindow(s, t) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit