76. Minimum Window Substring (Hard)
https://leetcode.com/problems/minimum-window-substring/
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"
Note:
- If there is no such window in S that covers all characters in T, return the empty string
""
. - If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
Solutions
class Solution {
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0) {
return "";
}
// used to keep the count of the unique characters in t.
Map<Character, Integer> tCountMap = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
int count = tCountMap.getOrDefault(t.charAt(i), 0);
tCountMap.put(t.charAt(i), count + 1);
}
// Number of unique characters in t, which need to be present in the desired window.
int reqChar = tCountMap.size();
// formedChar is used to keep track of how many unique characters in t
// are present in the current window in its desired frequency.
// e.g. if t is "AABC" then the window must have two A's, one B and one C.
// Thus formedChar would be = 3 when all these conditions are met.
int formedChar = 0;
// Dictionary which keeps an account of all the unique characters in the current window.
Map<Character, Integer> windowCountMap = new HashMap<>();
// ans list of the form (window length, left, right)
int[] ans = {-1, 0, 0};
// Left and Right pointer
int lptr = 0;
int rptr = 0;
while (rptr < s.length()) {
// Add one character from the right to the window
char c = s.charAt(rptr);
int count = windowCountMap.getOrDefault(c, 0);
windowCountMap.put(c, count + 1);
// If the frequency of the current character in current window equals to the
// desired count in t, then increase the formedChar count by 1.
// Be careful, it's not >= but ==, only add once after meets the desired count.
if (tCountMap.containsKey(c) && windowCountMap.get(c).intValue() == tCountMap.get(c).intValue()) {
formedChar++;
}
// Try to shrink the candidate window until it becomes the minimum sub set.
// Prune the leftmost character if possible to minimize the length of candidate substring.
while (lptr <= rptr && formedChar == reqChar) {
// Update the smallest window if possible.
if (ans[0] == -1 || (rptr - lptr + 1) < ans[0]) {
ans[0] = rptr - lptr + 1;
ans[1] = lptr;
ans[2] = rptr;
}
c = s.charAt(lptr);
// Reduce the count of lptr character since it is no longer a part of the window.
windowCountMap.put(c, windowCountMap.get(c) - 1);
if (tCountMap.containsKey(c) && windowCountMap.get(c).intValue() < tCountMap.get(c).intValue()) {
formedChar--;
}
// Move the left pointer forward, this would help to look for a new window.
// The new window are expected to has a more compact substring.
// AAABC will be sorted out at first, then try to prune head chars if possible
lptr++;
}
// Keep expanding the window on the rptr side once we are done shrinking.
rptr++;
}
return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
}
}