☕ DSA Java Articles

Topics › Sliding Window and Two Pointers › Hard Problems

Minimum Window Substring

Hard TUF ID 931 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given two strings s (length n) and t (length m), return the shortest substring of s that contains every character of t, including duplicates. If t contains two 'a's, the window must contain at least two 'a's. If no such window exists, return the empty string "". When several shortest windows exist, return the leftmost one (LeetCode guarantees the answer is unique).

Constraints: 1 ≤ n, m ≤ 10^5, and both strings consist of English letters, so a 256-entry count table covers every character.

Example 1

s = "ADOBECODEBANC", t = "ABC"
answer = "BANC"     // the only length-4 window with an A, a B and a C

Example 2

s = "a", t = "aa"
answer = ""         // t needs two a's; s has only one

Approach 1: Brute force

Intuition. For each start i, extend j until s[i..j] covers t. The first such j gives the shortest valid window starting at i, because extending further only makes it longer. Keep the shortest over all starts.

To test coverage in O(1) per step, keep a table need[c]: how many more copies of c we still need. It starts as the character counts of t. Also keep missing, the total number of required characters not yet covered, starting at m. When s[j] arrives:

The window covers t exactly when missing == 0.

Algorithm.

  1. If m > n, return "".
  2. For each start i: rebuild need from t; missing = m.
  3. For j = i ..: update need and missing for s[j]. When missing == 0, compare j - i + 1 with the best, then break.
  4. Return the best window or "".
static String bruteForce(String s, String t) {
    int n = s.length(), m = t.length();
    if (m == 0 || m > n) return "";
    int bestLen = Integer.MAX_VALUE, bestStart = -1;
    for (int i = 0; i < n; i++) {
        int[] need = new int[256];
        for (int c = 0; c < m; c++) need[t.charAt(c)]++;
        int missing = m;                           // characters of t not yet covered by s[i..j]
        for (int j = i; j < n; j++) {
            if (need[s.charAt(j)] > 0) missing--;
            need[s.charAt(j)]--;
            if (missing == 0) {                    // shortest valid window that starts at i
                if (j - i + 1 < bestLen) {
                    bestLen = j - i + 1;
                    bestStart = i;
                }
                break;
            }
        }
    }
    return bestStart == -1 ? "" : s.substring(bestStart, bestStart + bestLen);
}

Complexity. Time O(n · (n + m)): for each of the n starts we rebuild the table in O(m) (plus a constant 256) and scan up to n characters. Space O(1): the table has a fixed size.

The waste: after finding that s[i..j] covers t, the next start i + 1 re-scans almost the same characters. The window s[i+1..j] is what we should test next, not a fresh scan from i + 1.

Approach 2: Optimal, expand and contract

Intuition. Coverage is monotonic. If s[l..r] covers t, so does every window containing it. If it does not, neither does any window inside it. That gives the two-pointer rhythm:

  1. Expand r until the window covers t. Now s[l..r] is valid but possibly bloated on the left.
  2. Contract l while the window still covers t, recording the length each time. When dropping s[l] breaks coverage (a required copy left the window), stop and go back to expanding.

Every valid window that could be the answer is examined: for each right end r, the contraction stops at the largest l for which s[l..r] still covers t, which is the shortest valid window ending at r. And neither pointer ever moves backwards, so the total work is linear.

The same need table and missing counter from Approach 1 make every step O(1). When removing s[l], increment need[s[l]]; if it becomes positive, that copy was required (not surplus), so missing increases.

Algorithm.

  1. If m > n, return "". Build need from t; missing = m; l = 0.
  2. For each r: if need[s[r]] > 0, missing--; then need[s[r]]--.
  3. While missing == 0: record s[l..r] if shorter than the best; need[s[l]]++; if it is now positive, missing++; l++.
  4. Return the best window or "".
static String optimal(String s, String t) {
    int n = s.length(), m = t.length();
    if (m == 0 || m > n) return "";
    int[] need = new int[256];                     // need[c] > 0: still missing; < 0: surplus copies in the window
    for (int c = 0; c < m; c++) need[t.charAt(c)]++;
    int missing = m, l = 0, bestLen = Integer.MAX_VALUE, bestStart = -1;
    for (int r = 0; r < n; r++) {
        if (need[s.charAt(r)] > 0) missing--;
        need[s.charAt(r)]--;
        while (missing == 0) {                     // window s[l..r] covers t: record, then try to shrink
            if (r - l + 1 < bestLen) {
                bestLen = r - l + 1;
                bestStart = l;
            }
            need[s.charAt(l)]++;
            if (need[s.charAt(l)] > 0) missing++;  // we just dropped a required copy
            l++;
        }
    }
    return bestStart == -1 ? "" : s.substring(bestStart, bestStart + bestLen);
}

Dry run on s = "ADOBECODEBANC", t = "ABC" (only the steps where the window becomes valid):

r char valid window on entry windows recorded while shrinking coverage breaks when dropping best
5 C “ADOBEC” (0..5) “ADOBEC” A at 0 “ADOBEC”
10 A “DOBECODEBA” (1..10) “DOBECODEBA” down to “CODEBA” C at 5 “ADOBEC”
12 C “ODEBANC” (6..12) “ODEBANC” down to “BANC” B at 9 “BANC”

At r = 10 the new A restores coverage. Contraction drops D, O, B, E (the B at index 3 is surplus because another B sits at index 9) and stops once the C at index 5 leaves. Its shortest record, "CODEBA", only ties "ADOBEC" and does not replace it. At r = 12 the new C restores coverage; contraction from l = 6 peels O, D, E and records "BANC" before the B at index 9 leaves.

Complexity. Time O(n + m): building the table costs m, and l and r each move at most n times. Space O(1): a fixed 256-entry table.

Edge cases and pitfalls