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 範圍內的都要補回來，這是這個技巧的基本