Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such 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.

Example 1:

Input: s = “ADOBECODEBANC”, t = “ABC” Output: “BANC” Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.

Example 2:

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

Example 3:

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 <= 105
• s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Approach: Sliding Window with Two Pointers

Algorithm

1. Build a frequency map for characters in t
2. Expand the window with a right pointer, tracking how many required characters are satisfied
3. When the window contains all characters of t, shrink from the left while validity is maintained
4. Record the smallest valid window
5. Return the substring of the smallest recorded window, or "" if none

Time & Space Complexity

• Time Complexity: O(m + n) - each character is processed at most twice
• Space Complexity: O(m + n) - the frequency maps for s and t

Java Implementation

import java.util.HashMap;
import java.util.Map;

public class MinimumWindowSubstring {

    /**
     * Return the minimum window substring of s that contains all of t.
     * @param s Source string
     * @param t Target characters (with duplicates)
     * @return Minimum window substring or empty string
     */
    public static String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> window = new HashMap<>();
        int required = need.size();
        int formed = 0;

        int left = 0;
        int minLen = Integer.MAX_VALUE;
        int start = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);

            if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {
                formed++;
            }

            while (formed == required) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }

                char leftChar = s.charAt(left);
                window.put(leftChar, window.get(leftChar) - 1);
                if (need.containsKey(leftChar) && window.get(leftChar) < need.get(leftChar)) {
                    formed--;
                }
                left++;
            }
        }

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

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: s = \"ADOBECODEBANC\", t = \"ABC\"");
        System.out.println("Output: \"" + minWindow("ADOBECODEBANC", "ABC") + "\""); // Expected: "BANC"

        System.out.println("Input: s = \"a\", t = \"a\"");
        System.out.println("Output: \"" + minWindow("a", "a") + "\""); // Expected: "a"

        System.out.println("Input: s = \"a\", t = \"aa\"");
        System.out.println("Output: \"" + minWindow("a", "aa") + "\""); // Expected: ""
    }
}

Example Walkthrough

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

1. Expand until the window covers A, B, C: "ADOBEC" (length 6)
2. Shrink from the left while still valid: "DOBEC" -> not valid, stops
3. Continue expanding; eventually "BANC" (length 4) is the smallest valid window
4. Return "BANC"

Key Points

1. Duplicates Matter: t can require multiple copies of the same character
2. Formed vs Required: The window is valid when formed == required
3. Integer Comparison: Use .intValue() or intValue() when comparing counts to avoid Integer caching pitfalls
4. Shrink Phase: After finding a valid window, keep shrinking to find a smaller one
5. O(m + n): The follow-up bound is met by the sliding window approach