Find minimum window in s containing all characters of t.
Input: s="ADOBECODEBANC", t="ABC" → Output: "BANC"
Input: s="a", t="a" → Output: "a"
Sliding window with frequency maps. Expand right until all chars covered, then shrink left.
- Count required frequencies from t
- Sliding window: expand right adding chars
- When all required chars satisfied: try shrinking left
- Update minimum window when valid
- Return minimum window substring
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>(), have = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
int formed = 0, required = need.size();
int left = 0, minLen = Integer.MAX_VALUE, minStart = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
have.merge(c, 1, Integer::sum);
if (need.containsKey(c) && have.get(c).equals(need.get(c))) formed++;
while (formed == required) {
if (right - left + 1 < minLen) { minLen = right - left + 1; minStart = left; }
char lc = s.charAt(left++);
have.merge(lc, -1, Integer::sum);
if (need.containsKey(lc) && have.get(lc) < need.get(lc)) formed--;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}
- Time Complexity: O(n+m)
- Space Complexity: O(n+m)