Minimum Window Substring Hard 0 attempts
LeetCode ↗

Minimum Window Substring

Hard StringHash Table LeetCode

Given two strings s and t, locate the shortest contiguous substring of s that includes every character from t, matching duplicate counts as well. If no such substring is present, return an empty string instead.

Whenever a valid window exists, there's exactly one smallest one that satisfies the condition.

Input Format
Implement minWindow(s, t). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
s = "a"
t = "aa"
Output
""
Constraints
  • 1 <= s.length, t.length <= 10^5
  • s and t consist of uppercase and lowercase English letters
Test Cases (2)
Case 1
Args: ["ADOBECODEBANC","ABC"] Expected: "BANC"
Case 2
Args: ["a","aa"] Expected: ""
Topics
StringHash Table

Sliding window with two pointers. Build a frequency map for t. Expand the right pointer until the window satisfies all requirements, then shrink from the left to find the tightest valid window. Track how many distinct characters are fully satisfied to avoid recounting the entire map each step.

javascript
function minWindow(s, t) {
  if (t.length > s.length) return '';

  const need = new Map();
  for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);

  let have = 0;
  const required = need.size;
  const window = new Map();
  let minLen = Infinity;
  let minStart = 0;
  let left = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    window.set(ch, (window.get(ch) || 0) + 1);

    if (need.has(ch) && window.get(ch) === need.get(ch)) {
      have++;
    }

    while (have === required) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        minStart = left;
      }
      const leftCh = s[left];
      window.set(leftCh, window.get(leftCh) - 1);
      if (need.has(leftCh) && window.get(leftCh) < need.get(leftCh)) {
        have--;
      }
      left++;
    }
  }

  return minLen === Infinity ? '' : s.substring(minStart, minStart + minLen);
}

Time: O(|s| + |t|) — each pointer traverses the string at most once. Space: O(|s| + |t|) for the hash maps.

Saved in this browser only. Private to you.

JavaScript