76. Minimum Window Substring
- tags
- sliding window, subarray
- source
- leetcode
Edge Cases
"aa"
"aa"
"aaflslflsldkalskaaa"
"aaa"
"abc"
"a"
Solution
class Solution {
public String minWindow(String s, String t) {
int[] count = new int[128];
char[] sArray = s.toCharArray();
char[] tArray = t.toCharArray();
int found = 0, required = 0;
for (char c: tArray) {
count[c]++;
required++;
}
int minL = -1, minR = -1;
for (int l = 0, r = 0; r < sArray.length; r++) {
count[sArray[r]]--;
if (count[sArray[r]] >= 0) found++;
if (found == required) {
while (count[sArray[l]] != 0) count[sArray[l++]]++;
if (minR == -1 || (r - l) < (minR - minL)) {
minR = r;
minL = l;
}
count[sArray[l++]]++;
found--;
}
}
return minR == -1 ? "" : s.substring(minL, minR + 1);
}
}
Complexity
- time: O(N)
- space: O(N + M)