Back to DSA
Minimum Window Substring
hardTwo strings are provided: a source string and a required-characters string. Find the smallest contiguous window within the source that includes every character from the required-characters string, respecting duplicate counts. If no valid window exists, return an empty string. The answer is guaranteed to be unique when it exists.
Examples
Example 1:
Input:
source = "XAYBEZCAD", required = "ABC"Output:
"BEZCA"Explanation: The window from index 3 to 7 is 'BEZCA', which contains one each of A, B, and C. No shorter window covers all three.
Example 2:
Input:
source = "x", required = "xx"Output:
""Explanation: The source has only one 'x' but two are required, so no valid window exists.
Hints
import java.util.*;
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
int left = 0, valid = 0, start = 0, minLen = Integer.MAX_VALUE;
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()) valid++;
while (valid == need.size()) {
if (right - left + 1 < minLen) {
start = left;
minLen = right - left + 1;
}
char d = s.charAt(left);
if (need.containsKey(d) && window.get(d).intValue() == need.get(d).intValue()) valid--;
window.merge(d, -1, Integer::sum);
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
}Time complexity
O(m + n)Space complexity
O(m + n)