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

 

Constraints:

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

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int l1 = s1.length(), l2 = s2.length();
        int[] hash = new int[256];
        char[] st1 = s1.toCharArray();
        char[] st2 = s2.toCharArray();
        for(char c : st1) hash[c]++;
        int l = 0, count = 0;
        
        for(int r = 0; r < l2; r++) {
            hash[st2[r]]--;
            if(hash[st2[r]] >= 0) count++;
            
            while(r - l + 1 > l1) {
                hash[st2[l]]++;
                if(hash[st2[l]] > 0) count--;
                l++;
            }
            if(count == l1) return true;
        }
        return false;
    }
}

sliding window, 因为要判断s1的permutation在不在s2中，所以window长度就应该是s1.length(),问题在window怎么动。这里就用r - l + 1, 大于l1了就要动，然后更新l和hash数组。