# LeetCode 567. Permutation in String

https://leetcode.com/problems/permutation-in-string/description/

## 題目大意

給定兩字串 `s1` 跟 `s2` ，如果 `s1` 的 permutation 為 `s2` 之子字串回傳 `true` 否則回傳 `false`

兩字串皆只由小寫英文字母組成

## 思考

這題很明顯我們可以用 sliding window 解題
關鍵就是我們有明確的**連續長度**要比較： `s1.length()`

我們可以用一個長度 26 的 array 來記錄 `s1` 之字母出現頻率
並且我們使用 `remaining` 記錄 `s1` 的組成字符是否已經耗盡 (全都被找到)

class Solution
{
public:
    bool checkInclusion(const string &s1, const string &s2)
    {
        const int n1 = s1.length(), n2 = s2.length();
        if (n1 > n2)
            return false;

        array<int, 26> cnt{};
        int remaining = n1;

        for (const char c1 : s1)
        {
            ++cnt[c1 - 'a'];
        }

        for (int i = 0; i < n2; ++i)
        {
            if (--cnt[s2[i] - 'a'] >= 0)
                --remaining;

            if (i >= n1)
            {
                if (++cnt[s2[i - n1] - 'a'] > 0)
                    ++remaining;
            }

            if (!remaining)
                return true;
        }

        return false;
    }
};

對於 `s2` 中的前 `n1` 長之子字串 我們可以放心去檢查是否能用盡 `s1` 的組成
只要在這段長度內有用盡，就表示這整段即 `s1` 之 permutation

但當我們已經超出 `[0, n1 - 1]` 這段範圍時表示 sliding window 該移動了， sliding window 移出後不在 window 範圍內的都要補回來，這是這個技巧的基本