# 567. Permutation in String (Sliding window)

[**567. Permutation in String**](https://leetcode.com/problems/permutation-in-string/description/)

 Given two strings **s1** and **s2**, write a function to return true if **s2** contains the permutation of **s1**. In other words, one of the first string's permutations is the **substring** of the second string.

**Example 1:**

```
Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").
```

**Example 2:**

```
Input:s1= "ab" s2 = "eidboaoo"
Output: False
```

**Note:**

1. The input strings only contain lower case letters.
2. The length of both given strings is in range \[1, 10,000].

**My Solutions:**

用 sliding window的思想，用array储存char出现的评率，比较每个s1.length() 长度的window，s1 和s2是否一样

```
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        
        int[] arr1 = new int[26], arr2 = new int[26];
        
        // 建字典，储存s1长度的字符出现频率
        for (int i = 0; i < s1.length(); i++) {
            arr1[s1.charAt(i) - 'a']++;
            arr2[s2.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < s2.length() - s1.length(); i++) {
            if (match(arr1, arr2)) return true;
            arr2[s2.charAt(i) - 'a']--; // arr2里当前字母的频率减1 --> sliding window的左边少一格
            arr2[s2.charAt(i + s1.length()) - 'a']++; // sliding window的右边多一格
        }
        
        return match(arr1, arr2);
    }
    
    // 检查两个数组是否存有相同字母
    public boolean match(int[] arr1, int[] arr2) {
        for (int i = 0; i < 26; i++) {
            if (arr1[i] != arr2[i]) return false;
        }
        return true;
    }
}
```