Leetcode 76: Minimum Window Substring

1. Problem Statement (Simple Explanation)

You’re given two strings:

• s (length m)

• t (length n)

You must find the minimum window substring of s that contains every character in t, including duplicates.

• If no such window exists, return "".

• It’s guaranteed that if an answer exists, it is unique.

Characters:

• Both s and t contain only uppercase and lowercase English letters.

Goal (follow-up): O(m + n) time.

2. Examples

Example 1:

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

Valid windows that cover "ABC" include:

• "ADOBEC" (covers A, B, C)

• "DOBECODEBA" (longer)

• "BANC" (B at index 9, A at 10, N at 11, C at 12)

The minimum such window is "BANC".

Output: "BANC"

Example 2:

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

Only window "a".

Output: "a"

Example 3:

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

t requires two 'a's, but s has only one → no valid window.

Output: ""

3. Approach – Sliding Window with Frequency Counters (O(m + n))

This is a classic sliding window problem:

We want the smallest substring of s that contains all characters of t with counts.

Key Ideas:

1. Use a frequency map need for characters in t:

need[c] = count of c in t

2. Use another map window to count characters inside our current window [left, right) in s.

3. Use two pointers:

• left (window start)

• right (window end, inclusive index or exclusive depending on implementation)

4. Maintain:

• required = number of distinct characters in t we need to satisfy.

• formed = number of distinct characters for which the window has at least the required count.

5. Algorithm outline:

• Expand right one character at a time, update window counts.

• When the current character’s count matches need, increment formed.

• Once formed == required (our window is “valid”, i.e. contains all characters with required counts):

• Try to shrink from the left:

• Update the best (minimum) window if current is smaller.

• Remove s[left] from window.

• If after removal, a required character count is no longer satisfied (window[c] < need[c]), decrement formed.

• Move left forward.

• Continue expanding right and shrinking left as above.

Because every character in s is visited at most twice (once when right expands, once when left shrinks), this runs in O(m + n).

Data Structures

Since s and t consist only of letters [A-Za-z], we can:

• Use an array of size 128 (or 256) for ASCII counts, or

• Use unordered_map / dict.

Here we’ll use array (index by char’s ASCII).

Pseudo-code:

Complexity:

Let:

• m = len(s)

• n = len(t)

Then:

• Preprocessing t: O(n)

• Sliding window over s: each index visited at most twice → O(m)

• Total: O(m + n)

• Space:

• need[128], window[128] → O(1) (constant)

4. Java code

5. C code

6. C++ code

7. Python code

8. JavaScript code

9. Java (alternative using HashMap) - for explanation clarity 

If you prefer using Map<Character, Integer>:

• Same logic, but use maps instead of fixed-size arrays.

• Time is still O(m + n), but with slightly more overhead.