Sliding Window
- Longest Substring Without Repeating Characters
- Minimum Size Subarray Sum
- Minimum Window Substring (hard)
- Longest Substring with At Most Two Distinct Characters (hard)
- Longest Substring with At Most K Distinct Characters
1. Longest Substring Without Repeating Characters
two pointers + map: char --> latest appearance index
the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward.
注意：abba的话，在right pointer 遇到第二个a的时候，left pointer 有可能回去，所以left = Math.max(left, map.get(c) + 1);
2. Minimum Size Subarray Sum
forward right pointer first and then move left pointer
先移动right pointer直到sum >= s了，这时候，这个subarray就满足条件了。然后再放弃最左边的数，去寻找新的组合。
3. Minimum Window Substring
参考模板（点击上方链接）涵盖了问题3， 4， 5
if (s == null || s.length() <= 1) return s.length();
int[] counter = new int[256];
int distinct = 0;
int left = 0;
int max = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (counter[c] == 0) distinct++;
counter[c]++;
while (distinct > 2) {
//update length here if find minimum
if (counter[s.charAt(left)] == 1) distinct--;
counter[s.charAt(left)]--;
left++;
}
//update length here if find maximum
if (right - left + 1 > max) {
max = right - left + 1;
}
}
return max;
}
One thing needs to be mentioned is that when asked to find maximum substring, we should update maximum after the inner while loop to guarantee that the substring is valid. On the other hand, when asked to find minimum substring, we should update minimum inside the inner while loop.
public String template(String s, String t) {
if (s.length() < t.length()) return "";
int[] balance = new int[256];
for (char c: t.toCharArray()) balance[c]--;//negative means the character is missing
int stringBalance = -t.length();
int min = Integer.MAX_VALUE;
int stringStart = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (balance[c] < 0) stringBalance++;
balance[c]++;
while (stringBalance == 0) {
if (right - left + 1 < min) {
min = right - left + 1;
stringStart = left;
}
if (balance[s.charAt(left)] == 0) stringBalance--;
balance[s.charAt(left)]--;
left++;
}
}
return min == Integer.MAX_VALUE ? "" : s.substring(stringStart, stringStart + min);
}
跟方法1差不多的思路
方法1
左右两个pointer，右边每次移动一个，如果当前的substring包含了所有的characters，那么移动左Pointer直到substring不再包含所有的character(也就是，overallBalance是负数)。
one int[256] record
class Solution {
public String minWindow(String s, String t) {
if(s == null || t == null || s.length() == 0 || t.length() == 0) return "";
char[] input = s.toCharArray();
// elementBalance[i] = # of element i that's required for a "valid" window
// elementBalance[i] < 0 We saw element i less times than required in the current window
// elementBalance[i] == 0 We saw element i exactly as many times as required in the current window
// elementBalance[i] > 0 We saw element i more times than required in the current window
// Note: We only care about elementBalance of required elements and ignore the balance of other elements that were found
int[] elementBalance = new int[128];
// Update balances of required elements
for(char requiredElement : t.toCharArray()) {
elementBalance[requiredElement]--; // Negative because we haven't found them yet
}
// Total # of required elements found in the current window
int overallBalance = -t.length(); // Negative because we haven't found them yet
// Tracks the min window found so far
int minWindowStartIndex = 0;
int minWindowLength = Integer.MAX_VALUE;
int curWindowStartIndex = 0;
for(int curWindowEndIndex=0; curWindowEndIndex < input.length; curWindowEndIndex++) {
char curElement = input[curWindowEndIndex];
if(elementBalance[curElement] < 0) { // If this is a required element
overallBalance++; // We have found a required element
}
elementBalance[curElement]++;
// While all required elements are in the current window
while(overallBalance == 0) {
// Updated minimum window found if needed
int curWindowLength = curWindowEndIndex-curWindowStartIndex+1;
if(curWindowLength < minWindowLength) {
minWindowLength = curWindowLength;
minWindowStartIndex = curWindowStartIndex;
}
// Shrink (minimize) this window size by incrementing the start index
char elementToRemove = input[curWindowStartIndex];
curWindowStartIndex++;
if(elementBalance[elementToRemove] == 0) { // We're losing the minimum required# of this element
overallBalance--;
}
elementBalance[elementToRemove]--;
}
}
return minWindowLength == Integer.MAX_VALUE ? "" : s.substring(minWindowStartIndex,minWindowStartIndex+minWindowLength);
}
}
方法2:
int[256] record + two pointers（太慢了，淘汰了）
分别用两个int[256]来记录target & source的字母。初始left, right = 0, 推进right直到找到substring或者到了尾巴。找到后，记录下长度和substring，再把left往前移一格，同时source[]对应的位置要-1。source[]主要是记录当前两个指针中间的字母。
O(n)，因为两个pointers只会往前移，只过了一边source。
4. Longest Substring with At Most Two Distinct Characters
int[256] counter + two pointers
如果遇到了第三个letter，则开始移动left pointer。每次移动的时候，对应的occurence - 1，这样子，最终两个字母当中的一个会先被耗尽完。比如“aabbbbaac”，当right pointer到了c，Left pointer开始往右移，最后当b都消耗完了，就是left听下的时候了，也就是紧跟在b后面的a。