Hard

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.

Examples

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

Output:"BANC"

The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

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

Output:"a"

The entire string s is the minimum window.

Constraints

m == s.length
n == t.length
1 <= m, n <= 10^5
s and t consist of uppercase and lowercase English letters.

Sliding Window with Target Frequencies

Approach

First, count frequencies of characters in `t`. Use a sliding window on `s`, tracking character frequencies in the current window. Keep a `have` count (characters that meet frequency requirement) and `need` count (total unique characters in `t`). When `have == need`, the window is valid. Shrink the window from the left while it remains valid to find the minimum length, updating the best result.

Complexity Analysis

Time Complexity

O(m + n)

Space Complexity

O(1)

Space is bounded by the size of the character set (e.g., 52 for English letters), thus effectively O(1).

Solution.java

1class Solution {2    public String minWindow(String s, String t) {3        if (s.isEmpty() || t.isEmpty() || s.length() < t.length()) return "";4        5        Map<Character, Integer> countT = new HashMap<>();6        for (char c : t.toCharArray()) {7            countT.put(c, countT.getOrDefault(c, 0) + 1);8        }9        10        int have = 0, need = countT.size();11        Map<Character, Integer> window = new HashMap<>();12        13        int left = 0;14        int minLen = Integer.MAX_VALUE;15        int[] minSpan = {-1, -1}; // [start, end]16        17        for (int right = 0; right < s.length(); right++) {18            char c = s.charAt(right);19            window.put(c, window.getOrDefault(c, 0) + 1);20            21            if (countT.containsKey(c) && window.get(c).equals(countT.get(c))) {22                have++;23            }24            25            while (have == need) {26                // Update result if smaller window found27                if ((right - left + 1) < minLen) {28                    minLen = right - left + 1;29                    minSpan[0] = left;30                    minSpan[1] = right;31                }32                33                // Pop from the left34                char leftChar = s.charAt(left);35                window.put(leftChar, window.get(leftChar) - 1);36                37                if (countT.containsKey(leftChar) && window.get(leftChar) < countT.get(leftChar)) {38                    have--;39                }40                left++;41            }42        }43        44        return minLen == Integer.MAX_VALUE ? "" : s.substring(minSpan[0], minSpan[1] + 1);45    }46}