[567] 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False

注意：

1. 输入的字符串只包含小写字母
2. 两个字符串的长度都在 [1, 10,000] 之间 ```cpp class Solution { public: bool checkInclusion(string s1, string s2) {

    if(s1.size() > s2.size()){
        return false;
    }
    int left = 0, right = 0;
    unordered_map<char, int> need, window;
    for(char c : s1) need[c]++;
    int valid = 0;
    for(int i = 0; i<s1.size() - 1;i++){
        char c = s2[right];
        right++;
        if(need.count(c)){
            window[c]++;
            if(window[c] == need[c]){
                valid++;
            }
        }
    }
   

    while(right < s2.size()){
        char c = s2[right];
        right++;
        if(need.count(c)){
            window[c]++;
            if(window[c] == need[c]){
                valid++;
            }
        }
        if(valid == need.size()){
            return true;
        }
        char t = s2[left];
        left++;
        if(need.count(t)){
            if(window[t] == need[t]){
                valid--;
            }
            window[t]--;
        }
    }

    return false;

}

}; ```