# 567 - Permutation in String

## 解法一 - Sliding Window + multiset

``````class Solution {
public:
bool checkInclusion(string s1, string s2) {
multiset<char> patternSet, excessSet;
for(auto c:s1) {
patternSet.insert(c);
}

int windowStart = 0;
for(int windowEnd = 0; windowEnd < s2.length(); windowEnd++) {
if(s1.find(s2[windowEnd]) != string::npos)
patternSet.erase(s2[windowEnd]);
else
excessSet.insert(s2[windowEnd]);

while(windowEnd - windowStart + 1 > s1.length()) {
if(s1.find(s2[windowStart]) != string::npos)
patternSet.insert(s2[windowStart]);
else
excessSet.erase(s2[windowStart]);

windowStart++;
}

if(patternSet.empty() && excessSet.empty())
return true;
}

return false;
}
};
``````

## 解法二 - Sliding Window + Hash Table

``````class Solution {
public:
bool checkInclusion(string s1, string s2) {
unordered_map<char, int> table;
for(auto c:s1)
table[c]++;

int windowStart = 0, matched = 0;
for(int windowEnd = 0; windowEnd < s2.length(); windowEnd++) {
char endChar = s2[windowEnd];
if(table.find(endChar) != table.end()) {
table[endChar]--;
if(table[endChar] == 0) {
matched++;
}
}

if(windowEnd - windowStart + 1 > s1.length()) {
char startChar = s2[windowStart++];
if(table.find(startChar) != table.end()) {
if(table[startChar] == 0)
matched--;

table[startChar]++;
}
}

// Note that this equals to table.size()
// instead of s1.legnth() because there might be duplicate chars in s1
if(matched == table.size())
return true;
}

return false;
}
};
``````

Runtime: 16 ms, faster than 47.09% of C++ online submissions for Permutation in String. Memory Usage: 9.4 MB, less than 93.75% of C++ online submissions for Permutation in String.