Sliding window problem review

---

Of course, it can be in B Stand and find some teaching videos to learn

Heart A Scholar algorithm

Ancient city algorithm teaching

Simply speaking ; The idea of sliding windows is

(1) When the current conditions are not met , Expand to the right , When the conditions are met , Shrink the left border to the right , Get a solution and save it temporarily ,
(2) The first step of the cycle , Get another solution , Compare it with the first solution , Get the optimal solution and store it temporarily , And so on , Stop until the window reaches the right boundary .

1. Start with the basic problem

1.1 Power button [3]: Longest substring without repeating characters

Original link : Longest substring without repeating characters

 Given a string  s , Please find out that there are no duplicate characters in it   Longest substrings   The length of .
 Example  1:
 Input : s = "abcabcbb"
 Output : 3 
 explain :  Because the longest substring without repeating characters is  "abc", So its length is  3.

 Example  2:
 Input : s = "bbbbb"
 Output : 1
 explain :  Because the longest substring without repeating characters is  "b", So its length is  1.

 Example  3:
 Input : s = "pwwkew"
 Output : 3
 explain :  Because the longest substring without repeating characters is  "wke", So its length is  3.
      Please note that , Your answer must be   Substring   The length of ,"pwke"  Is a subsequence , Not substring .
     
 Example  4:
 Input : s = ""
 Output : 0
 
 Tips ：
0 <= s.length <= 5 * 104
s  By the English letters 、 Numbers 、 Symbols and spaces 

 source ： Power button （LeetCode）
 link ：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Use sliding window to solve

class Solution {
    
 public int lengthOfLongestSubstring(String s) {
    
     // Slide window idea ;
     // Step right in the string ; If there is repetition, the left boundary shrinks ;
     int n = s.length();
     if(n<2)
       return n;
     
     // Here, we can use character array to mark char character ;
     // Use int[]  Array to count the frequency of characters ;
     char[] cArr = s.toCharArray();
     //s  By the English letters 、 Numbers 、 Symbols and spaces ;
     int[] nums = new int[128];
     
     // Two pointers to the window ;
     int left  = 0;
     int right = 0;
     // The result is at least 1;
     int res = 1;
     // As long as the window does not exceed the bounds of the string ; Can operate ;
     while(right<n){
    
         // Record the frequency of the current character ;
         nums[cArr[right]]++;
         // Note that if the sliding is repeated, the left pointer boundary will be contracted ;
         while(nums[cArr[right]]==2){
    
             nums[cArr[left]]--;
             left++;
         }
         // Calculated length ;
         res = Math.max(res,right-left+1);
         right++;
     }
     return res; 
 }
}

Also available set Non repetition of sets , Solve with pointer

class Solution {
    
 public int lengthOfLongestSubstring(String s) {
    
     // String matching process ;
     if(s==null || s.length()==0) 
        return 0;
     // Pointer solution ;
     
     Set<Character> set = new HashSet<>();

     int zhen = -1; int res =0;
     for(int i =0;i<s.length();++i){
    
         if(i!=0){
    
             set.remove(s.charAt(i-1));
         }
         // Move without repetition ;
         while(zhen+1<s.length() && !set.contains(s.charAt(zhen+1))){
    
             set.add(s.charAt(zhen+1));
             ++zhen;
         }
         // The length of the non repeating characters in this segment ;
         res = Math.max(res,zhen-i+1);
     }
     return res;
 }
}

---

1.2 Power button [209]: Subarray with the smallest length

Original position : Subarray with the smallest length

 Given a containing  n  An array of positive integers and a positive integer  target .
 Find the sum of the array  ≥ target  The smallest length of  
 Continuous subarray  [numsl, numsl+1, ..., numsr-1, numsr] , And return its length .
 If there is no sub array that meets the conditions , return  0 .

 Example  1：
 Input ：target = 7, nums = [2,3,1,2,4,3]
 Output ：2
 explain ： Subarray  [4,3]  Is the smallest subarray in this condition .

 Example  2：
 Input ：target = 4, nums = [1,4,4]
 Output ：1

 Example  3：
 Input ：target = 11, nums = [1,1,1,1,1,1,1,1]
 Output ：0
 
 Tips ：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

 source ： Power button （LeetCode）
 link ：https://leetcode-cn.com/problems/minimum-size-subarray-sum
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The sliding window

class Solution {
    
 public int minSubArrayLen(int target, int[] nums) {
    
     // Slide window idea ;
     int left  = 0;
     int right = 0;
     int n = nums.length;
     int sum = 0;
     // Set a default length ;
     int len = Integer.MAX_VALUE;
     while(right < n){
    
         // First move the right pointer , Add data ;
         sum+=nums[right];
         // if >= The target ; Because we need to satisfy the shortest subarray , Then shrink the left boundary ;
         while(sum>=target){
    
             len = Math.min(len,right - left +1);
             // Shrink the left border ;
             sum -= nums[left];
             left++;
         }
         right ++;
     }
     // because len Initialized to the maximum ; Here we need to exclude ;
     if(len == Integer.MAX_VALUE){
    
         return 0;
     }
     return len;
 }
}

---

2. Other questions

Basically, the idea of sliding window is used ; Additional requirements need to be considered ;

2.1 Power button [424] : The longest repeated character after replacement

Original link : The longest repeated character after replacement

 Given a string  s  And an integer  k .
 You can select any character in the string , And change it to any other uppercase English characters . This operation can be performed up to  k  Time .
 After doing this , return   The length of the longest substring containing the same letter  .

 Example  1：
 Input ：s = "ABAB", k = 2
 Output ：4
 explain ： With two 'A' Replace with two 'B', vice versa .

 Example  2：
 Input ：s = "AABABBA", k = 1
 Output ：4
 explain ：
 Will the middle one 'A' Replace with 'B', The string changes to  "AABBBBA".
 Substring  "BBBB"  There is the longest repeating letter ,  The answer for  4.
 
 Tips ：
1 <= s.length <= 105
s  It's made up of lowercase letters 
0 <= k <= s.length

 source ： Power button （LeetCode）
 link ：https://leetcode-cn.com/problems/longest-repeating-character-replacement
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Using the slide window , Match gradually to the right , At the same time, record the number of repeated characters in the current window ; If in Replace k Time after , Approximate to the length of the window ; Then the length of the current window meets the conditions , Return to ;

class Solution {
    
    public int characterReplacement(String s, int k) {
    
        int len = s.length();
        if(len < 2) return len;
        // String to array ;
        char[] Arr = s.toCharArray();
        // An array that records character frequencies ;
        int[] temp = new int[128];
        // When the window slides , The current number of characters in the window at this time ;
        int tempCount =0;
        // final result ;
        int res = 0;
        // Sliding pointer ;
        int left  = 0;
        int right = 0;
        while(right < len){
    
            temp[Arr[right]]++;
            // Record the number ;
            tempCount = Math.max(tempCount,temp[Arr[right]]);
            right ++;
            // If the current character cannot fill the window , You need to shrink the left window ;
            if(tempCount+k < right - left){
    
                temp[Arr[left]]--;
                left++;
            }
            // Record the length at this time ;
            res = Math.max(res,right - left);
        }
        return res; 
    }
}

---

2.2 Power button [76] : Minimum cover substring

Original position : Minimum cover substring

-  Give you a string  s 、 A string  t .
-  return  s  Covered by  t  The smallest string of all characters .
-  If  s  There is no coverage in  t  Substring of all characters , Returns an empty string  "" .

 Be careful ：
 about  t  Duplicate characters in , The number of characters in the substring we are looking for must not be less than  t  The number of characters in the .
 If  s  There is such a substring in , We guarantee that it is the only answer .
 
 Example  1：
 Input ：s = "ADOBECODEBANC", t = "ABC"
 Output ："BANC"

 Example  2：
 Input ：s = "a", t = "a"
 Output ："a"

 Example  3:
 Input : s = "a", t = "aa"
 Output : ""
 explain : t  Two characters in  'a'  Shall be included in  s  In the string of ,
 Therefore, there is no qualified substring , Returns an empty string .
 
 Tips ：
1 <= s.length, t.length <= 105
s  and  t  It's made up of English letters 

 source ： Power button （LeetCode）
 link ：https://leetcode-cn.com/problems/minimum-window-substring
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Parent string matching child string problem , Use the window to find the starting position of the matching character ;

How to ensure that matching characters are equal ?
- Use the character statistics array to count the number of occurrences of the current character , If it is consistent, it means it matches ;

class Solution {
    
    public String minWindow(String s, String t) {
    
        //.... at that time   Didn't pay attention to , hold faLen  and sonLen All the lengths are used s Of , Wrong shooting for a long time ;
        //s: Parent string , t: Substring ;
        int faLen  = s.length();
        int sonLen = t.length();
        // Special circumstances exclude ;
        if(faLen < sonLen){
    
            return "";
        }
        // Here, first change the two strings into character arrays ;
        char[] FaArr  = s.toCharArray();
        char[] SonArr = t.toCharArray();
        // An array used to count the number of character frequencies ;
        int[] FaCount  = new int[128];
        int[] SonCount = new int[128];
        // The substring is fixed , Then give it directly ;
        for(char c:SonArr){
    
            SonCount[c]++;
        }
        // Record the current row in the window   The number of substring character types included ;
        int FaDistance = 0;
        // The sliding window ;
        int left = 0;
        int right = 0;
        // The length of the string that satisfies the condition in the parent string ;
        int goodLen = Integer.MAX_VALUE;
        // The qualified index starting point in the parent string ;
        int begin = 0;
        while(right < faLen){
    
            // The current number of characters is the same ; Then increase the number of types of parent string ;
            if(FaCount[FaArr[right]] < SonCount[FaArr[right]]){
    
                 FaDistance ++;
            }
            // Record the number of times the current character appears ;
            FaCount[FaArr[right]]++;
            // The parent string moves to the right first ;
            right++;
            // Be careful ; If you have completely found the child string in the parent string ; Consider starting optimization ;
            while(FaDistance == sonLen){
    
                // Here is the length , At the same time, record the starting point of the left window ;
                if(goodLen > right-left){
    
                    goodLen = right-left;
                    begin = left;
                }
                // If the number of characters corresponding to the left pointer has matched the number of substrings ; Then the number of types of strings decreases ;
                if(FaCount[FaArr[left]] == SonCount[FaArr[left]]){
    
                    FaDistance --;
                }
                FaCount[FaArr[left]]--;
                // The left window is indented ;
                left++;
            }
        }
        // Here, we need to judge the length of the satisfied substring ;
        if(goodLen ==Integer.MAX_VALUE ){
    
            return "";
        }
        // Intercept the matching string ;
        return s.substring(begin,begin+goodLen);
    }
}

---

2.3 Power button [438] : Find all alphabetic words in the string

Original position : Find all alphabetic words in the string

 Given two strings  s  and  p, find  s  All in  p  Of   Heterotopic words   The string of ,
 Returns the starting index of these substrings . Regardless of the order of the answer output .
 Heterotopic words   A string formed by rearrangement of the same letters （ Include the same string ）.

 Example  1:
 Input : s = "cbaebabacd", p = "abc"
 Output : [0,6]
 explain :
 Start index equals  0  The substring is  "cba",  It is  "abc"  The heterotopic words of .
 Start index equals  6  The substring is  "bac",  It is  "abc"  The heterotopic words of .

  Example  2:
 Input : s = "abab", p = "ab"
 Output : [0,1,2]
 explain :
 Start index equals  0  The substring is  "ab",  It is  "ab"  The heterotopic words of .
 Start index equals  1  The substring is  "ba",  It is  "ab"  The heterotopic words of .
 Start index equals  2  The substring is  "ab",  It is  "ab"  The heterotopic words of .
 
 Tips :
1 <= s.length, p.length <= 3 * 104
s  and  p  Only lowercase letters 

 source ： Power button （LeetCode）
 link ：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

This question , stay 76 Based on the question , Minor changes ,
Which exactly matches the substring Length and character ;

class Solution {
    
    public List<Integer> findAnagrams(String s, String p) {
    
        List<Integer> list = new ArrayList<>();
        // Sliding window problem ;
        int FaLen  = s.length();
        int SonLen = p.length();
        if(FaLen<SonLen){
    
            return list;
        } 
        // First convert the substring into an array ;
        char[] SonArr = p.toCharArray();
        // An array that counts the number of string frequencies ;
        int[] FaCount = new int[128];
        int[] SonCount= new int[128];
        // Count the number of character occurrences of the substring ;
        for(char c : SonArr){
    
            SonCount[c]++;
        }
        // The number of character types matched in the parent string ;
        int FaDistance =0;
        // The current number of character types of the substring ;
        int SonDistance = 0;
        for(int i =0;i<SonCount.length;i++){
    
            if(SonCount[i]>0){
    
                SonDistance+=1;       
            }
        }
        int left =0;
        int right =0;
        while(right < FaLen){
    
            // Slide the window to the right first ;
            char rightChar = s.charAt(right);
            // If the current substring has this character, then act ;
            if(SonCount[rightChar]>0){
    
                FaCount[rightChar]++;
                if(FaCount[rightChar] == SonCount[rightChar]){
    
                    FaDistance++;
                }
            }
            right++;
            // When the substring length is matched ;
            while(FaDistance == SonDistance){
    
                // Mark the appropriate starting point ;
                if(SonLen == right-left){
    
                    list.add(left);
                }
                char leftChar = s.charAt(left);
                // The left window shrinks ;
                if(SonCount[leftChar]>0){
    
                    FaCount[leftChar]--;
                    if(FaCount[leftChar]<SonCount[leftChar]){
    
                      FaDistance--;
                    }
                }
                left++;
            }
        }
        
        return list;
    }
}

---

2.4 Power button [ 567] Arrangement of strings

Original position : Arrangement of strings

 Here are two strings  s1  and  s2 ,
 Write a function to judge  s2  Does it include  s1  Permutation .
 If it is , return  true ; otherwise , return  false .
 let me put it another way ,s1  One of the permutations is  s2  Of   Substring  .

 Example  1：
 Input ：s1 = "ab" s2 = "eidbaooo"
 Output ：true
 explain ：s2  contain  s1  One of the permutations of  ("ba").

 Example  2：
 Input ：s1= "ab" s2 = "eidboaoo"
 Output ：false
 
 Tips ：
1 <= s1.length, s2.length <= 104
s1  and  s2  Only lowercase letters 

 source ： Power button （LeetCode）
 link ：https://leetcode-cn.com/problems/permutation-in-string
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

and 438 The solution of the problem is consistent ;

class Solution {
    
    public boolean checkInclusion(String s1, String s2) {
    
        // Actually sum 438 Same question ;
        //s1: Substring ; s2: Parent string ;
        int SonLen  = s1.length();
        int FaLen   = s2.length();
        if(FaLen < SonLen){
    
            return false;
        }
        // String to array ;
        char[]  SonArr = s1.toCharArray();
        // An array of statistical character ratings ;
        int[] SonCount = new int[128];
        int[] FaCount  = new int[128];
        // Number of types of parent string ;
        int FaDistance  =0;
        // The number of types of substrings ;
        int SonDistance =0;
        // First give the substring ;
        for(char c:SonArr){
    
            SonCount[c]++;
        }
        for(int i =0;i<SonCount.length;i++){
    
            if(SonCount[i]>0){
    
                SonDistance+=1;
            }
        }
        // Sliding pointer ;
        int left  = 0;
        int right = 0;
        while(right<FaLen){
    
            // If there are characters in the substring, operate again ;
            char rightChar = s2.charAt(right);
            if(SonCount[rightChar]>0){
    
                FaCount[rightChar]++;
                if(FaCount[rightChar]==SonCount[rightChar]){
    
                    FaDistance++;
                }
            }
            right++;
            // When the number of types of parent string matches enough ;
            while(FaDistance == SonDistance){
    
               // If it matches the sequence ; Go straight back to ;
               if(right - left == SonLen){
    
                   return true;
               }
               // The left border is ready to shrink ;
               char leftChar = s2.charAt(left);
               if(SonCount[leftChar]>0){
    
                   FaCount[leftChar]--;
                   if(FaCount[leftChar] < SonCount[leftChar]){
    
                       FaDistance --;
                   }
               }
               left++;
            }
        }
        return false;
    }
}

---