76. Minimum Window Substring

NeetCode: Minimum Window Substring · LeetCode: 76. Minimum Window Substring · Difficulty: Hard

Given strings s and t, return the shortest substring of s that contains every character of t, including duplicates. Return "" if none exists.

Example

Input:  s = "OUZODYXAZV", t = "XYZ"    Output: "YXAZ"
Input:  s = "xyz",        t = "xyz"    Output: "xyz"
Input:  s = "x",          t = "xy"     Output: ""

Brute force: check every substring

Generate substrings in order of increasing length and return the first that covers t. The 128-slot count arrays assume ASCII characters, as in LeetCode's constraints (English letters). s.charAt(i) is a char, which Java widens to the int array index.

class Solution {
    private boolean covers(String s, int start, int len, int[] need) {
        int[] have = new int[128];
        for (int i = start; i < start + len; i++) {
            have[s.charAt(i)]++;
        }
        for (int c = 0; c < 128; c++) {
            if (have[c] < need[c]) {
                return false;
            }
        }
        return true;
    }

    public String minWindow(String s, String t) {
        int[] need = new int[128];
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        for (int len = t.length(); len <= s.length(); len++) {
            for (int start = 0; start + len <= s.length(); start++) {
                if (covers(s, start, len, need)) {
                    return s.substring(start, start + len);
                }
            }
        }
        return "";
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minWindow("OUZODYXAZV", "XYZ"));
        System.out.println(sol.minWindow("xyz", "xyz"));
        System.out.println("[" + sol.minWindow("x", "xy") + "]");
    }
}

YXAZ
xyz
[]

Time: O(n³): O(n²) substrings, each checked in O(n). Space: O(1).

Optimal: expand right, shrink left

Track two things: need[c], how many more copies of character c the window still wants, and missing, how many characters of t are still not covered in total. When missing == 0, the window is valid.

1. Start with need[c] = count of c in t, and missing = t.length().
2. Move right forward and add s.charAt(right). If need for that character was above 0, it is a useful character, so missing -= 1. Always do need[c] -= 1 (it goes negative for extras).
3. While missing == 0, the window [left, right] is valid: record it if it is the shortest so far, then remove s.charAt(left): need[c] += 1, and if that makes it above 0 a needed character was lost, so missing += 1. Move left forward.
4. Each character enters and leaves once, so both pointers only move forward.

class Solution {
    public String minWindow(String s, String t) {
        if (t.isEmpty()) {
            return "";
        }
        int[] need = new int[128];
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        int missing = t.length();
        int left = 0;
        int bestStart = 0;
        int bestLen = -1; // -1 means no valid window yet

        for (int right = 0; right < s.length(); right++) {
            char added = s.charAt(right);
            if (need[added] > 0) {
                missing--;
            }
            need[added]--;

            while (missing == 0) {
                if (bestLen == -1 || right - left + 1 < bestLen) {
                    bestStart = left;
                    bestLen = right - left + 1;
                }
                char removed = s.charAt(left);
                need[removed]++;
                if (need[removed] > 0) {
                    missing++;
                }
                left++;
            }
        }
        return bestLen == -1 ? "" : s.substring(bestStart, bestStart + bestLen);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minWindow("OUZODYXAZV", "XYZ"));
        System.out.println(sol.minWindow("xyz", "xyz"));
        System.out.println("[" + sol.minWindow("x", "xy") + "]");
        System.out.println("[" + sol.minWindow("abc", "") + "]");
    }
}

YXAZ
xyz
[]
[]

Time: O(n + m). Space: O(1) (a 128-entry array), plus the returned substring.

need[c] goes negative for letters that appear more often in the window than t requires. Only a value above zero means a needed letter is still missing, which is why missing changes only when need[c] > 0 before the decrement or after the increment. The early return handles an empty t (otherwise missing starts at 0 and every window would count as valid). bestLen = -1 marks "no window found", and substring copies only the final answer.

How to explain it in an interview

• Say first: check every substring against t, shortest first; that is O(n^3).
• Key insight: a window that is valid stays valid when it grows on the right, so expand until valid, then shrink from the left as far as possible; pointers never move back.
• Code it in steps: (1) need counts from t and missing = t.length(); (2) for each right, decrement missing if the character was still needed, then need[c] -= 1; (3) while missing == 0, record the best window; (4) undo s.charAt(left) (need += 1, missing += 1 if it becomes positive) and advance left; (5) return the best substring or "".
• Complexity to state: O(n + m) time, O(1) space for ASCII.
• Likely follow-ups / pitfalls: duplicates in t (why need can go negative); input beyond ASCII would need a larger array or a HashMap<Character, Integer> instead of the 128-slot array.