Given strings s and t, return the minimum window in s that contains all characters of t. If no such window exists, return empty string.
Input: s="ADOBECODEBANC", t="ABC" → Output: "BANC"Input: s="a", t="a" → Output: "a"
Sliding window with character frequency maps. Expand right until window contains all t chars, then shrink from left to minimize window while still valid.
- Build frequency map for t (need[]).
- Expand right: add s[right] to window map, if it satisfies a needed char increment formed count.
- When formed == required (all chars satisfied): try shrinking left, update min window.
- Shrink: remove s[left] from window map; if needed char drops below required, decrement formed.
import java.util.*;
class Solution {
public String minWindow(String s, String t) {
int[] need = new int[128], have = new int[128];
int required = 0;
for (char c : t.toCharArray()) { need[c]++; if (need[c] == 1) required++; }
int formed = 0, left = 0, minLen = Integer.MAX_VALUE, start = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
have[c]++;
if (need[c] > 0 && have[c] == need[c]) formed++;
while (formed == required) {
if (right - left + 1 < minLen) { minLen = right - left + 1; start = left; }
have[s.charAt(left)]--;
if (need[s.charAt(left)] > 0 && have[s.charAt(left)] < need[s.charAt(left)]) formed--;
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
}
- Time Complexity: O(|S| + |T|)
- Space Complexity: O(|S| + |T|)