Minimum Window Substring
This is a simple problem if the string T
only contains disctinct characters.
However, based on the solution to simple problem, we can get this problem's solution easily.
We apply sliding window method and use two count array to hold character counts in T
and current slinding
window in S
respectively. We uses a int variable to count how many characters in the sliding
window is less than or equal to character counts in T
. That is, for a character c
, we only
count it when the number it appears is less than that in T
. When moving the right pointer
to narrow the window we also only decrease count when the number drops below that in T
.
public class MinimumWindowSubstring {
public String minWindow(String s, String t) {
if (t.isEmpty()) return t;
int[] tcount = new int[128];
int[] scount = new int[128];
int matchcount = 0;
for (int i = 0; i < t.length(); i++) {
tcount[t.charAt(i)]++;
}
int i = 0;
int j = 0;
String res = "";
while (j < s.length()) {
char chj = s.charAt(j++);
scount[chj]++;
if (scount[chj] <= tcount[chj]) matchcount++;
while (matchcount >= t.length()) {
if (res.isEmpty() || j - i < res.length()) res = s.substring(i, j);
char chi = s.charAt(i++);
scount[chi]--;
if (scount[chi] < tcount[chi]) matchcount--;
}
}
return res;
}
}