Sliding Window 题目的进一步归类

Sliding Window: Generalized
Code Template
        int i = 0;
        for (int j = 0; j < n; j++) {
             // update state of the window after adding j into the window
             f[s.charAt(j)]++;  
             max = Math.max(max, f[s.charAt(j)]);

            // moving left pointer to make sure the window is always valid
             while (j - i + 1 - max > k) {
                 f[s.charAt(i)]--;
                 i++;
             }
             // update result
             res = Math.max(res, j-i+1);
         }
        return res;

Example
424. Longest Repeating Character Replacement
340 Longest Substring with At Most K Distinct Characters
3. Longest Substring Without Repeating Characters
1004. Max Consecutive Ones III
424. Longest Repeating Character Replacement
532. K-diff Pairs in an Array
923. 3Sum With Multiplicity
209. Minimum Size Subarray Sum
76. Minimum Window Substring
30. Substring with Concatenation of All Words
Number of subarrays with sum less than K
* subarray must contain only non-negative numbers, otherwise sliding window won’t work
1156. Swap For Longest Repeated Character Substring
* a window is defined as by having at most one swap, all chars in the window can be the same
* window become invalid when the window size is more than the number of most frequent char in the window + 1 (where 1 is the allowed swap) or the window size is more than the total freq of the most frequent char in the window
1234. Replace the Substring for Balanced String (slightly different than the traditional sliding window template)


Sliding Window: Fixed length
Pattern
right pointer - left pointer + 1 should be fixed size n
Example
438. Find All Anagrams in a String
567.Permutation In String
1151. Minimum Swaps to Group All 1's Together
220. Contains Duplicate III


Sliding Window: Stack
Pattern
The elements in the window are put into stack, stack can be viewed as the state of current window


Example:
1081. Smallest Subsequence of Distinct Characters

多谢分享，辛苦了，先收藏了。