leetcode-08

The sliding window

class Solution {
     public static List<Integer> findAnagrams(String s,String p){
        int slength=s.length();
        int plength=p.length();
        ArrayList<Integer> result = new ArrayList<>();
        if(slength<plength) return result;
        int[] sCnt = new int[26];
        int[] pCnt = new int[26];
        //1. initialization p Word frequency array and s Word frequency array of , Next two positions 
        for (int i = 0; i < plength; i++) {
            pCnt[p.charAt(i)-'a']++;
            sCnt[s.charAt(i)-'a']++;
        }
        //2. Make an initial judgment 
        if (Arrays.equals(sCnt,pCnt)){
            result.add(0);
        }
        //3. Traverse p Judge , Because I judged once before , Clear the left side every time you judge , Then move to the right once , Make a second judgment 
        for (int i =plength; i < slength; i++) {
            sCnt[s.charAt(i-plength)-'a']--;
            sCnt[s.charAt(i)-'a']++;
            if (Arrays.equals(sCnt, pCnt)) {
                result.add(i-plength+1);
            }
        }
        return result;
    }
}

class Solution {
        public int characterReplacement(String s, int k) {
            int[] num = new int[26];
            int n = s.length();
            int maxn = 0;
            //left: Left boundary , Used to subtract the head or calculate the length when sliding 
            //right: Right border , Used to add a window tail or calculate the length 
            int left = 0, right = 0;
            while (right < n) {
                int indexR = s.charAt(right) - 'A';
                num[indexR]++;
                // Find the maximum number of times a letter has appeared in the window 
                // Calculate the maximum number of times a letter appears in a window , The window length can only be increased or unchanged （ Pay attention to the back left The pointer just moved 0-1 Time ）
                // The significance of doing so ： We want the longest , If you can't find a longer hold length, the return result will not be affected 
                maxn = Math.max(maxn, num[indexR]);
               
                // length len=right-left+1, hereinafter referred to as len
                //len- Maximum number of letter occurrences > Number of replacements  => len> Maximum number of letter occurrences + Number of replacements 
                // Look at the , The number of substitutions is constant =k, The maximum number of letters is possible to change , therefore , Only the maximum number of letters increases ,len To get the maximum 
                // Without meeting the conditions ,left and right Move together ,len constant 
                if (right - left + 1 - maxn > k) {
                    // Here we need to reduce , because left Cross this point , Will affect the maximum value 
                    num[s.charAt(left) - 'A']--;
                    left++;
                }
                // After walking here , Actually right Will take one more step 
                right++;
            }
            // because right Take one more step , The result is (right-1)-left+1==right-left
            return right - left;
        }
}