Sliding Window

1. edge cases

2. char note

3. iterate string:

   • add char

   • window formed

   • move left side char, move window

   • until window do not satisfy, repeat

4. two kinds of sliding window: 1) flexible length, usually max/min; 2) fixed length, usually find something.

flexible window

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

https://leetcode.com/problems/minimum-window-substring/description/

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/description/

https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/description/

https://leetcode.com/problems/minimum-window-substring/description/

https://leetcode.com/problems/minimum-size-subarray-sum

https://leetcode.com/problems/subarray-product-less-than-k/description/

https://leetcode.com/problems/max-consecutive-ones-ii/discuss/96920/Java-clean-solution-easily-extensible-to-flipping-k-zero-and-follow-up-handled

https://leetcode.com/problems/longest-repeating-character-replacement/description/

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        // edge cases
        if (s == null || s.length() == 0 || k <= 0) return 0;

        // build note
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int l = 0, r = 0, lgst = 0, cnt = 0;

        // iterate
        for (; r < s.length(); r++) {
            char c = s.charAt(r);
            map.put(c, map.getOrDefault(c, 0) + 1);
            if (map.get(c) == 1) cnt++;  // new character appear in current window

            while (cnt > k) {  // one window formed
                lgst = Math.max(lgst, r - l);  // store length
                char lc = s.charAt(l);
                map.put(lc, map.get(lc) - 1);
                l++;  // remove left char, move window

                if (map.get(lc) == 0) cnt--;  // reduce one char count 
            }
        }
        lgst = Math.max(lgst, r - l);  // update last window value

        // result
        return lgst;
    }
}

fixed window

https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/

https://leetcode.com/problems/sliding-window-maximum/description/ https://leetcode.com/problems/sliding-window-median/description/ https://leetcode.com/problems/find-all-anagrams-in-a-string/description/ https://leetcode.com/problems/permutation-in-string/description/

https://leetcode.com/problems/k-empty-slots https://leetcode.com/problems/can-place-flowers/description/