76. Minimum Window Substring

This is the hard end of the sliding-window family. If Longest Substring Without Repeating Characters is the version where the window grows and shrinks on one simple rule, this one adds a twist: you expand until the window is valid, then shrink to make it minimal — and knowing when it’s valid is the whole game.

Question

Given two strings s and t of lengths m and n respectively,

• returnthe minimum window substring of ssuch that every character in t (including duplicates) is included in the window.
• If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

• Example1

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation:
The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

• Example2

Input: s = "a", t = "a"
Output: "a"
Explanation:
The entire string s is the minimum window.

• Example3

Input: s = "a", t = "aa"
Output: ""
Explanation:
Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

• Constraints
  • $m == s.length$
  • $n == t.length$
  • $1 <= m, n <= 10^5$
  • s and t consist of uppercase and lowercase English letters.
• Follow-up:
  • Could you find an algorithm that runs in $O(m + n)$ time?

Algorithm

• Sliding Window
  • TC: $O(m + n)$
  • SC: $O(1)$

Answer

1. Start with two pointers left and right both pointing to the first element of s.

2. Expand the window by moving right until the window contains all characters of t.

3. Once a valid window is found, shrink it by moving left forward. Keep updating the minimum window size while the window remains valid.

4. When the window becomes invalid, repeat step 2.

// Sliding Window
// TC: O(m + n)  where m = s.length(), n = t.length()
// SC: O(1)  (fixed-size arrays of 128 chars)
public String minWindow(String s, String t) {
    if (s == null || t == null) return "";
    int[] need = new int[128];
    int[] have = new int[128];

    for (char c : t.toCharArray()) need[c]++;

    int required = t.length();
    int formed = 0;
    int left = 0;
    int minLen = Integer.MAX_VALUE;
    int minStart = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        have[c]++;
        // Count character only if it's still needed
        if (need[c] > 0 && have[c] <= need[c]) formed++;

        // Shrink window from the left while it's valid
        while (formed == required) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }
            char leftChar = s.charAt(left);
            have[leftChar]--;
            if (need[leftChar] > 0 && have[leftChar] < need[leftChar]) formed--;
            left++;
        }
    }

    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}

Explain

Substring vs Subsequence

Substring — contiguous characters in s

s = "ADOBECODEBANC"
          [BANC]     ← contiguous ✓
          [B  C]     ← non-contiguous ✗

Subsequence — order preserved, but gaps allowed

s = "ADOBECODEBANC"
     A   B  C        ← order maintained, gaps allowed ✓

What this problem actually requires

The window found in s must be a Substring (contiguous), but the characters of t can appear in any order inside that window.

s = "ADOBECODEBANC", t = "ABC"

window "BANC" → contiguous in s ✓
               contains A, B, C in any order ✓

The code checks this with frequency counts, not order:

int[] need = new int[128];  // how many of each char t requires
int[] have = new int[128];  // how many of each char the window has

If t’s characters had to appear in order, this would be a Subsequence problem (e.g. LeetCode 392).

The formed == required trick

The subtle part is knowing when the window is valid without rescanning it every step. Two counters do it. required is t.length() — the total characters you still owe, duplicates included. formed counts how many of those obligations are currently met.

The guard if (need[c] > 0 && have[c] <= need[c]) formed++ is the careful bit: a character only advances formed while the window still needs it. Once have[c] passes need[c], extra copies don’t count — they’re just slack the shrink phase will trim. When formed == required, every obligation is covered, so the window is valid and you can start pulling left inward. That’s what keeps the whole thing $O(m + n)$: each pointer moves forward at most m times, and the validity check is a couple of integer comparisons, never a rescan.

References

• https://leetcode.com/problems/minimum-window-substring/