567 Permutation in String

Leetcode

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

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

用一个数组计算剩下每个字母的个数，用一个整数 remain 计算剩余个数错误的字母。滑动窗口从左往右移动，若 remain 为 0 则匹配成功。

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