Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such substring exists, return the empty string.
Example 1
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: "BANC" is the smallest substring of s containing all of A, B, and C.
Example 2
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string is the minimum window.
Example 3
Input: s = "a", t = "aa"
Output: ""
Explanation: t requires two a's, s only has one — no valid window exists.
1 <= s.length, t.length <= 10^5s and t consist of uppercase and lowercase English lettersThis is the variable-size sliding window pattern at its hardest: the window must expand to satisfy a condition, then shrink as much as possible while still satisfying it.
Track how many of t's required characters (with correct counts) are currently satisfied in the window — a single integer counter, not a full re-scan, can tell you when the window is valid.
Once the window is valid, shrink from the left greedily until it's no longer valid, recording the smallest valid window seen along the way.
public String minWindow(String s, String t) {
if (s.isEmpty() || t.isEmpty()) return "";
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
Map<Character, Integer> window = new HashMap<>();
int required = need.size();
int formed = 0; // how many unique chars currently meet their required count
int left = 0, bestLen = Integer.MAX_VALUE, bestStart = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
window.merge(c, 1, Integer::sum);
if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {
formed++;
}
while (formed == required) {
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = 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 bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}Time: O(|s| + |t|) · Space: O(|s| + |t|)