# 0567. Permutation in String
###### tags: `Leetcode` `Medium` `Sliding Window`
Link: https://leetcode.com/problems/permutation-in-string/description/
## 思路
和[0438. Find All Anagrams in a String](https://hackmd.io/MvGWdMIxQZ26uuetxx6l_g)类似
### Sliding Window $O(l_1+26*l_2)$ $O(1)$
fixed length sliding window
记录sliding window里面每一个字母的count
每次挪动sliding window更新count 并且和s1的count比较 如果完全一样 返回true
### Optimized Sliding Window $O(l_1+l_2)$ $O(1)$
用一个变量match记录现在一共有多少个字母有一样的count 如果count=26 说明找到了match的string 返回true
## Code

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

Optimized

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if(s1.length()>s2.length()) return false;
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for(int i=0; i<s1.length(); i++){
            cnt1[s1.charAt(i)-'a']++;
        }
        int match = 0;
        for(int i=0; i<26; i++){
            if(cnt1[i]==cnt2[i]) match++;
        }
        for(int i=0; i<s2.length(); i++){
            int r = s2.charAt(i)-'a';
            if(cnt1[r]==cnt2[r]) match--;
            else if(cnt1[r]==cnt2[r]+1) match++;
            cnt2[s2.charAt(i)-'a']++;

            if(i>=s1.length()){
                int l = s2.charAt(i-s1.length())-'a';
                if(cnt1[l]==cnt2[l]) match--;
                else if(cnt1[l]==cnt2[l]-1) match++;
                cnt2[s2.charAt(i-s1.length())-'a']--;
            } 
            
            if(match==26) return true;
        }
        return false;
    }
}