# 567 - Permutation in String

解法一 - Sliding Window + multiset

這題主要就是要找到跟 pattern 一樣長，且包含的字母跟 pattern 一樣。所以我們可以用一個固定大小的 window 一次往後滑一個字母，然後用某種方法來判斷目前的 window 是否為 pattern 的 permutation：

用一個 multiset 來儲存 pattern 裡的 char - patternSet 用另一個 multiset 來儲存 sliding window 裡不在 pattern 中的 char - excessSet

然後每當擴張 sliding window，若新字母在 pattern 中，就去除掉 patternSet 的新字母，若不在，就加入 excessSet。如果 patternSet 跟 excessSet 都是空的，那表示目前的 window 是 permutation，回傳 true。

實作如下：

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

比起用 multiset，用 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.