Sliding Window

好题：

• Minimum Window Substring

• Longest substring without repeating characters

模板

• maintain a window = [begin, end] -> s.substring(begin, end +1)

• define what is a valid window

• move end pointer one step forward per iteration

• only move begin pointer when found a valid window

for (int end = 0; end < s.length(); end++) { 
    //proceed s.charAt(end)
    
    while window is still valid {
        //update res 
        //move begin pointer
    }
}

找最小window: while window is still valid

找最大window: while window is still invalid

为什么不用begin作iterator?

1. 因为如果iterator begin pointer的话最后both begin and end need to move to the end, which means each char has been visited by exact 2 times.

2. while if we iterate end pointer to the end, each char has been visited by at most 2 times(only when char is part of a valid window)

Minimum Window Substring

• sliding window模板题，多练

• move end pointer one step forward per iteration

• only move begin pointer when found a valid window

public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
            return "";
        }
        Map<Character, Integer> dict = new HashMap<>();
        for (char c : t.toCharArray()) {
            dict.put(c, dict.getOrDefault(c, 0) + 1);
        }
        int counter = 0;
        String res = s + t;
        int begin = 0;
        for (int end = 0; end < s.length(); end++) {
            //proceed s.charAt(end)
            char cur = s.charAt(end);
            Integer cnt = dict.get(cur);
            if (cnt != null) {
                dict.put(cur, cnt - 1);
                if (dict.get(cur) == 0) {
                    counter++;
                }
            }
            //while cur window is still a valid window
            while (counter == dict.size()) {
                //update res
                res = end - begin + 1 < res.length() ? s.substring(begin, end + 1) : res;
                //move begin
                char prev = s.charAt(begin);
                Integer count = dict.get(prev);
                if (count != null) {
                    dict.put(prev, count + 1);
                    if (dict.get(prev) == 1) {
                        counter--;
                    }
                }
                begin++;
            }
        }
        return res.length() == s.length() + t.length() ? "" : res;
    }

Find All Anagrams in a string

• sliding window end pointer模板

class Solution {
    /*
         **window [begin, end] -> s.substring(begin, end + 1)
         **valid window is an anagram of string p
         
        convert String p to a dict, char->freq
       
        move end pointer one step forward per iteration-> for loop
            deal with s.charAt(end)
            while window is valid {
                 update res
                deal with s.charAt(begin) before moving begin pointer one step forward
            }
        
    */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        //validate input
        if (s == null || s.length() < p.length()) {
            return res;
        }
        //convert to a map, char->cnt
        Map<Character, Integer> charToCnt = new HashMap<>();
        for (char c : p.toCharArray()) {
            charToCnt.put(c, charToCnt.getOrDefault(c, 0) + 1);
        }
        int counter = 0;
        int begin = 0;
        //move end pointer one step forward per iteration
        for (int end = 0; end < s.length(); end++) {
            char cur = s.charAt(end);
            Integer cnt = charToCnt.get(cur);
            //decrement cnt if charToCnt contains cur 
            if (cnt != null) {
                charToCnt.put(cur, cnt - 1);
                if (charToCnt.get(cur) == 0) {
                    counter++;
                }
            }
            //while window is valid
            while (counter == charToCnt.size()) {
                //update res
                if (end - begin + 1 == p.length()) {
                    res.add(begin);
                }
                //move begin
                char c = s.charAt(begin);
                Integer count = charToCnt.get(c);
                if (count != null) {
                    charToCnt.put(c, count + 1);
                    if (charToCnt.get(c) == 1) {
                        counter--;
                    }
                }
                begin++;
            }
        }
        return res;
    }
}

Longest substring without repeating characters

• find max window的模板题

• 重点在于how to define a valid window

• while window is invalid

class Solution {
    /*
    maintain a window[begin, end] ->consist of all unique char
    create a map to store all char in the window, char-> cnt
    valid window -> no dup char
    move end pointer one step forward per iteration
    increment cnt of cur char in the map
    window is invalid -> map.get(cur) > 1
    while window is invalid {
        //move begin pointer
    }
    update res for a valid window
    */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> charToCnt = new HashMap<>();
        int begin = 0;
        int len = 0;
        for (int end = 0; end < s.length(); end++) {
            char cur = s.charAt(end);
            charToCnt.put(cur, charToCnt.getOrDefault(cur, 0) + 1);
            //while window is invalid
            while (charToCnt.get(cur) > 1) {
                //move begin pointer
                char c = s.charAt(begin);
                charToCnt.put(c, charToCnt.get(c) - 1);
                begin++;
            }
            //update res
            len = Math.max(len, end - begin + 1);
        }
        return len;
    }
}

Longest Substring with at most 2 distinct character

• 组合题，一个思路

class Solution {
    /*
    window[begin, end]
    maintain a hashmap to store all char in the window, char->cnt
    window is valid -> set.size() <=2
    for (int end = 0; end < s.length(); end++) {
        //add s.charAt(end) to set
        while window is invalid{
            //move begin pointer
        }
        //update res when window is valid
    }
    */
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s.length() < 3) {
            return s.length();
        }
        int begin = 0;
        Map<Character, Integer> charToCnt = new HashMap<>();
        int len = 0;
        for (int end = 0; end < s.length(); end++) {
            char cur = s.charAt(end);
            charToCnt.put(cur, charToCnt.getOrDefault(cur, 0) + 1);
            //while window is invalid
            while (charToCnt.size() > 2) {
                //move begin
                char c = s.charAt(begin);
                int cnt = charToCnt.get(c);
                charToCnt.put(c, cnt - 1);
                if (charToCnt.get(c) == 0) {
                    charToCnt.remove(c);
                }
                begin++;
            }
            //update res
            len = Math.max(len, end - begin + 1);
        }
        return len;
    }
}

Longest Substring with at most K distinct character

• 和上一题的区别只是把2改成K

Longest Substring with at least K Repeating Character

• 从题目上看以为还是sliding window的思路，实际上是divide & conquer

• 先cnt所有char ,然后顺序遍历a~z, 如果cnt[i] == 0, skip to next char.

• if cnt[i] < k,说明最终返回的结果里肯定没有这个char,所以就遍历string找到这个char,然后recursive call s.substring(0, i) 和substring(i + 1),在返回的left和right中返回大的

class Solution {
    public int longestSubstring(String s, int k) {
        if (s == null || s.length() < k) {
            return 0;
        }
        if ( k < 2) return s.length();
        return helper(s.toCharArray(), 0, s.length(), k);
    }
    private int helper(char[] arr, int start, int end, int k) {
        if (end - start < k) return 0;
        int[] counts = new int[26];
        for (int i = start; i < end; i++) {
            counts[arr[i] - 'a']++;
        }
        boolean valid = true;
        for (int i = 0; i < 26; i++) {
            if (counts[i] > 0 && counts[i] < k) {
                valid = false;
                break;
            }
        }
        if (valid) {
            return end - start;
        }
        int res = 0, newStart = start;
        for (int i = start; i < end; i++) {
            if (counts[arr[i] - 'a'] < k) {
                res = Math.max(res, helper(arr,newStart, i, k));
                newStart = i + 1;
            }
        }
        res = Math.max(res, helper(arr,newStart, end, k));
        return res;
    }
}

Minimum Size Subarray Sum

• 简单修改下sliding window模板

• 每次先sum += nums[end], 然后checksum >= s的情况下, 再sum -= nums[begin++];

• Time: O(N), Space: O(1)

public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int N = nums.length;
        int sum = 0, size = N + 1;
        int begin = 0, end = 0;
        while (end < N) {
            sum += nums[end];
            while (sum >= s) {
                size = Math.min(size, end - begin + 1);
                sum -= nums[begin];
                begin++;
            }
            end++;
        }
        return size == N + 1 ? 0 : size;
    }

Contains Duplicates II

• 这题最直接的是用HashMap,O(N)& O(N),打败了67.39%

• 还可以用sliding window的思路解题设一个cur指针

• 建一个HashSet

• 当cur > k的时候，每次先删除nums[cur - k - 1]

• 再判断set.add(nums[cur])是否为false,从而判断是否contain duplicate within at most K distance,打败了97%

public boolean containsNearbyDuplicate(int[] nums, int k) {
        //hashset and sliding window
        if(nums == null || nums.length < 2) return false;
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            if(i > k){
                set.remove(nums[i - k - 1]);
            }
            if(!set.add(nums[i])) return true;
        }
        return false;
    }