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

Solution1：Sliding Window 两数组count

思路：
Time Complexity: O(N) Space Complexity: O(N)

Solution2：Sliding Window 写在一个数组里

思路：
Time Complexity: O(N) Space Complexity: O(N)

Solution1 Code：

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

Solution2 Code：

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