Minimum Window Substring

The problem

You are given two strings, text of length n and target_text of length m. Find the shortest substring of text that contains every character of target_text, with repeats: if target_text has two A’s, the substring needs at least two A’s. Return that substring, or "" if there is none.

A substring is a run of characters that sit next to each other. When there is an answer, it is unique.

Example 1

Input: text = "BXAYCAB", target_text = "ABC"

Output: "CAB"

“BXAYC” and “AYCAB” also hold A, B and C, but “CAB” does it in only 3 characters.

text

B0X1A2Y3C4A5B6

target_text

ABC

Example 2

Input: text = "aa", target_text = "aa"

Output: "aa"

target_text needs two a’s, so the window must be the whole string.

Example 3

Input: text = "q", target_text = "qq"

Output: ""

target_text needs two q’s, but text has only one. No window works.

Constraints

• 1 ≤ n, m ≤ 100,000
• text and target_text hold uppercase and lowercase English letters.

Clarifying questions

Do repeats in target_text count?

Yes. If target_text has two A's, the window needs at least two A's.

Does the order of target_text matter?

No. The window only needs the letters, in any order, with other letters mixed in.

Are uppercase and lowercase different?

Yes. "a" does not count as "A".

What if no window works?

Return the empty string "".

Spot the pattern

We want the shortest contiguous run that meets a rule: it covers target_text. If a window covers target_text, any bigger window around it covers target_text too. That is the sliding window pattern again, but this time we shrink while the window is valid, because we want the shortest, not the longest.

Solutions

Brute forceO(n²)Sliding windowO(n + m)

Show all

This problem has two approaches. Checking every substring from scratch would be O(n³), which is just a slower brute force.

Brute force O(n²)

The idea

Try every start i. Grow the window to the right one character at a time, counting the letters in it. As soon as the counts cover every letter of target_text, that window is the shortest one for this start, so record it if it beats the best and stop growing.

It is correct. But each start counts almost the same letters as the start before it.

Walkthrough

text

B0X1A2Y3C4A5B6

best

""

1. best = ""
2. for i in range(len(text)):
3. have = Counter()
4. for j in range(i, len(text)):
5. have[text[j]] += 1
6. if all(have[letter] >= need[letter] for letter in need):
7. if best == "" or j - i + 1 < len(best):
8. best = text[i : j + 1]
9. break
10. return best

For each start i, grow the window until it holds every letter of target_text = "ABC". The first such window is the shortest for that start.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: from every start, grow until the window holds all of targetText.
    // n starts, up to n steps each, and a check over 128 characters: O(n^2).
    public String minWindow(String text, String targetText) {
        int[] need = new int[128];
        for (char letter : targetText.toCharArray()) need[letter]++;
        String best = "";
        for (int i = 0; i < text.length(); i++) {
            int[] have = new int[128];
            for (int j = i; j < text.length(); j++) {
                have[text.charAt(j)]++;
                if (covers(have, need)) {
                    if (best.isEmpty() || j - i + 1 < best.length())
                        best = text.substring(i, j + 1);
                    // Growing further from i only makes the window longer.
                    break;
                }
            }
        }
        return best;
    }

    private boolean covers(int[] have, int[] need) {
        for (int letter = 0; letter < 128; letter++) if (have[letter] < need[letter]) return false;
        return true;
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines add one character to the counts and check whether the window covers target_text. They sit inside two loops. The check compares at most 52 letters (128 slots in the code), a fixed amount that never grows with n. So each run counts as 1 step.

   1. best = ""
   2. for i in range(len(text)):
   3. have = Counter()
   4. for j in range(i, len(text)):
   5. have[text[j]] += 1
   6. if all(have[letter] >= need[letter] for letter in need):
   7. if best == "" or j - i + 1 < len(best):
   8. best = text[i : j + 1]
   9. break
   10. return best

2. 2 Count the runs on Example 1

   Example 1 has 7 characters. The table counts the inner runs for each start: until the window covers target_text, or until the end of text when it never does.

   5 + 6 + 5 + 4 + 3 + 2 + 1 = 26 runs.

   start i	0	1	2	3	4	5	6
   inner runs	5	6	5	4	3	2	1

   total

   5 + 6 + 5 + 4 + 3 + 2 + 1 = 26

3. 3 Write the count for any n

   In the worst case no window covers target_text, so every start runs to the end:

   n + (n − 1) + … + 1 = n × (n + 1) / 2 = ½n² + ½n

   Check it with Example 1: that worst case would be 7 × 8 / 2 = 28 runs. The real 26 is lower because the first starts stop early. Counting target_text once at the start adds m more.

4. 4 Keep only the part that grows fastest

   • Drop the +½n, the ½ and the fixed cost of each check. None of them changes how fast the count grows.
   • The m is part of n². A window can only cover target_text if m ≤ n, and the n² part is far bigger.

   What is left is n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The code keeps two tables of counts, need and have, of 128 slots each, plus the best window. The tables never grow, so the extra space is O(1), besides the answer itself.

   need (up to 52 letters)have (up to 52 letters)bestij

Sliding window O(n + m)

The idea

Keep one window, from left to right, and a table need: for each letter, how many more copies the window still lacks. Also keep one number, missing, the total of the letters still lacked. The window covers target_text exactly when missing is 0. That way we never compare whole tables.

Move right one step at a time and take its letter into the window. If need for it was above 0, the window just gained a letter it lacked, so missing goes down.

While missing is 0, the window covers target_text. Record it if it is the shortest so far. Then give back the leftmost letter and move left right. If that letter was one target_text needed, need rises above 0 and missing goes up again, so the shrinking stops.

The invariant: each time the window stops shrinking, it was the shortest window that covers target_text and ends at right. The best of those is the answer.

Walkthrough

text

B0X1A2Y3C4A5B6

letter of target_text	A	B	C
still needed	1	1	1

missing

3

best

none yet

1. need = Counter(target_text); missing = len(target_text)
2. left = 0; best = None
3. for right, letter in enumerate(text):
4. if need[letter] > 0: missing -= 1
5. need[letter] -= 1
6. while missing == 0:
7. best = shorter of best and (left, right)
8. need[text[left]] += 1
9. if need[text[left]] > 0: missing += 1
10. left += 1
11. return text[best] if best else ""

"still needed" counts the letters of target_text the window lacks. missing = 3 is their total. The window covers target_text when missing is 0.

← BackStep →Play1 / 14

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Sliding window: grow right until it covers targetText, then shrink left while it still does.
    // Each letter enters and leaves once, so O(n + m) time.
    public String minWindow(String text, String targetText) {
        // need[letter] > 0 means the window still lacks that many copies of letter.
        int[] need = new int[128];
        for (char letter : targetText.toCharArray()) need[letter]++;
        int missing = targetText.length();
        int left = 0, bestStart = 0, bestLength = Integer.MAX_VALUE;
        for (int right = 0; right < text.length(); right++) {
            char letter = text.charAt(right);
            // Only a letter that targetText still lacks brings us closer.
            if (need[letter] > 0) missing--;
            need[letter]--;
            while (missing == 0) {
                if (right - left + 1 < bestLength) {
                    bestStart = left;
                    bestLength = right - left + 1;
                }
                // Give back the leftmost letter. If targetText needed it, the window breaks.
                char out = text.charAt(left);
                need[out]++;
                if (need[out] > 0) missing++;
                left++;
            }
        }
        if (bestLength == Integer.MAX_VALUE) return "";
        return text.substring(bestStart, bestStart + bestLength);
    }
}

Big O

Time O(n + m)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the for loop takes in one character. Each run of the while loop gives one back. Both change one count and maybe missing, which is 1 step. Before the loop, counting target_text costs one step per letter of target_text.

   1. need = Counter(target_text); missing = len(target_text)
   2. left = 0; best = None
   3. for right, letter in enumerate(text):
   4. if need[letter] > 0: missing -= 1
   5. need[letter] -= 1
   6. while missing == 0:
   7. best = shorter of best and (left, right)
   8. need[text[left]] += 1
   9. if need[text[left]] > 0: missing += 1
   10. left += 1
   11. return text[best] if best else ""

2. 2 Count the runs on Example 1

   Example 1 has n = 7 and m = 3. Counting target_text takes 3 steps. right then moves 7 times. left moves 5 times: once after “BXAYC”, then four times as the window shrinks from “XAYCAB” down to “AB”.

   3 + 7 + 5 = 15 steps.

   pointer	right (adds)	left (removes)
   moves on Example 1	7	5

   total

   3 to count target_text, then 7 + 5 = 12

3. 3 Write the count for any n

   right moves n times. left only moves forward and never passes right, so it moves at most n times in total:

   m (count target_text) + n (right) + at most n (left) ≤ m + 2n

   Check it with Example 1: 3 + 7 + 5 = 15, below 3 + 14 = 17.

4. 4 Keep only the part that grows fastest

   Drop the 2. A fixed factor does not change how the work grows. Both strings must be read, and they can grow on their own, so both stay: what is left is n + m.

   So the time is O(n + m).

5. S Space: count the extra memory the same way

   need has one slot per possible character, 128 in the code. That never grows, so the extra space is O(1). missing, left and the best window’s start and length are a fixed few numbers.

   need (up to 52 letters)missingleftbest

Common mistake

Lowering missing for every letter of target_text

Only lower missing when need[letter] was above 0. An extra copy of a letter, like the second A in “AYCAB”, is not progress. If you count it, missing reaches 0 too early and you return a window that does not cover target_text.

Tested at the limits

2,000 random pairs of texts made of a, A and b, so case matters, repeats in the target need repeats in the window, and many targets cannot be covered. The brute force and the sliding window gave the same answer every time.

Largest inputs	Result
100,000 letters in both texts (the most allowed). The target is the text shuffled, so the only window is the whole text. Sliding window.	0.02 s, and under 0.01 MB of extra memory: just the 52 counters.
100,000 letters with 1,000 random letters to cover, so the window grows and shrinks all the way along. Sliding window.	0.03 s, and under 0.01 MB of extra memory. The answer was checked to cover the target.
2,000 letters with 50 to cover. Brute force.	0.24 s. At 100,000 letters it would check about 5 billion windows, which is why the sliding window matters.