567. Permutation in String

Link

Solution

1. Permutation of a S1 is the list of string which has the same count for each character.

2. try to find a substring in S2, if their characters count are equal to S1's permutation

3. In this case, the sliding window's length is fixed to s1.length(), we move the sliding window for the begin of S2 to the end of S2

 public boolean checkInclusion(String s1, String s2) {
        int[] charsInS1 = new int[26];
        int[] charsInS2 = new int[26];
        
        if(s1.length() > s2.length()) return false;
        
        for(int i = 0; i < s1.length(); i++){
            charsInS1[s1.charAt(i) - 'a']++;
            charsInS2[s2.charAt(i) - 'a']++;
        }
        
        if(isMatch(charsInS1, charsInS2)) return true;
        
        for(int i = s1.length(); i < s2.length(); i++){
            charsInS2[s2.charAt(i) - 'a']++;
            charsInS2[s2.charAt(i - s1.length()) - 'a']--;
            if(isMatch(charsInS1, charsInS2)) return true;
        }
        return false;
        
    }
    
    public boolean isMatch(int[] charsInS1, int[] charsInS2){
        
        for(int i = 0; i < 26; i++){
            if(charsInS1[i] != charsInS2[i]) return false;
        }
        return true;
    }