Sliding Window Notes

05/07/2018 update:

关于l 和 r边界问题。l 是inclusive， r是exclusive。r是exclusive没有太大疑问，因为一开始检验后已经加1了。如果是求max, while结束后l刚好达到符合要求的index。 如果是求min, 在更新了检验变量后，如果还可以进入循环，证明l这个位置是符合条件的。

---------------------------------------------------------------------------------

Template

 Return Max

  

        while (r < s.length()) {
            // move right pointer
            while (condintion that breaks the requirement) {
                // move left pointer 
            }
            // update result
        }

Examples:

• longest substring with at most k distinct characters

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0) 
            return 0;
        int l = 0, r = 0, counter = 0, res = 0;
        int[] map = new int[256];
        while (r < s.length()) {
            if (map[s.charAt(r++)]++ == 0) counter++;
            // not satisfy
            while (counter > k) {
                // move left pointer
                if (map[s.charAt(l++)]-- == 1) counter--;
            }
            // update result
            res = Math.max(res, r - l);
        }
        return res;
    }
}

• longest substring without repeating characters

public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }

Return Min

 while(r < s.length()) {
            // update fast pointer
            while(satisfying condition) {
                // update res 
                // move slow pointer
            }
        }

Examples:

• minimum window substring

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0)
            return "";
        int l = 0, r = 0, start = 0, len = Integer.MAX_VALUE, count = t.length();
        int[] map = new int[256];
        for (char c: t.toCharArray()) {
            map[c]++;
        }
        
        while (r < s.length()) {
            if (map[s.charAt(r++)]-- > 0) count--;
            while (count == 0) {
                if (r - l < len) {
                    len = r - l;
                    start = l;
                }
                if (map[s.charAt(l++)]++ == 0) count++;
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

• minimum size subarray sum

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int res = Integer.MAX_VALUE;
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0,  sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (sum >= s) {
                res = Math.min(res, i - left + 1);
                sum -= nums[left++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

 Count source occurrence in target

1. Collect target's char counts in int[256] map
2. Set counter to target's length.
3. Since right pointer keeps subtracting map[s[r]], if s[r] is not in target, its count will < 0. If we meet map[s[r]] > 0, we encounters char in target, then counter--.
4. Same applies to left pointer, if map[s[l]] == 0, it means left pointer meets char in target. Chars that are not in target theirs count < 0. 

      Examples:

• Find All Anagarms in a String
• Permutation in String

         上面2道题本质是一样的。连代码都一样。当r移动到超过target string长度的时候需要移动l, 同时更新counter. 

  实现注意事项：

1. 我倾向于外层循环用while, 更新长度的时候直接用 r - l 就好了， 因为之前r已经加过了。
2. 可以先判断if(map[s.charAt(r)] > 0) 再舔更新if(map[s.charAt(r++)]-- > 0)。
3. 求min在第二层循环内更新结果，求max反之。
4. 统计出现次数是map[r]++, 统计occurrence是map[r]--