Command Palette

Search for a command to run...

Hectal
Problem 7.6 · Sliding WindowHard

Minimum Window Substring

PatternSliding Window: Variable SizeFrequency Counting

What it teaches: The full shortest-window machine: need counts, a satisfied counter, grow until valid, shrink while valid.

Practise it on judges as “Minimum Window Substring”.

The problem

Given strings s and t, return the shortest substring of s that contains every character of t (including duplicates). If none exists, return "". The answer is unique.

Example 1

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

Example 2

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

Example 3

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

Constraints

  • 1 ≤ s.length, t.length ≤ 10⁵
  • Upper and lowercase letters

Pattern clues in the wording

  • → "Minimum window" containing required characters
  • → Validity = counts meet requirements

These clues point to Sliding Window: Variable Size: Grow the window with the right pointer; when it breaks a rule, shrink it from the left until it's valid again.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128], have = new int[128];
        return "";
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
s = "ADOBECODEBANC"
t = "ABC"
"BANC"
2
s = "a"
t = "a"
"a"
3
s = "a"
t = "aa"
""

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: need counts + satisfied counter · O(|s| + |t|)
1

Optimal: need counts + satisfied counter

Time O(|s| + |t|) Space O(alphabet)

need[c] from t; required = number of distinct letters in t. Grow right: increment have[c], and if it just reached need[c], increment formed. While formed == required, record the window if shortest, then remove s[left]: if its count drops below need, decrement formed; advance left.

▶ Dry run: Finding "BANC"s = "ADOBECODEBANC", t = "ABC"
A
0
↑L
D
1
O
2
B
3
E
4
C
5
↑R
O
6
D
7
E
8
B
9
A
10
N
11
C
12

best(vars)

ADOBEC (6)

Step 1/4Grow until A, B and C are all inside: "ADOBEC" (length 6). Record it.

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

Verdict: Each character of s enters and leaves the window once.

Before you submit

Edge cases and common mistakes

Test these inputs

  • t longer than s
  • t has duplicate letters
  • No valid window
  • Answer is all of s

Mistakes people make

  • Incrementing formed every time a needed letter enters (not only when its count reaches the need).
  • Decrementing formed for letters t doesn't need (need[c] = 0).

Interview

Follow-up questions

Why check have[c] == need[c] exactly, not >=?