題目網址：https://leetcode.cn/problems/find-all-anagrams-in-a-string/

題意：給兩 string s 和 p, 找到 s 中所有 p 的異位詞, 並返回這些 substring 的起始 index。

異位詞：由相同字母重排列形成的 string（包括相同的 string）

Solution：

想法：利用 Sliding Window, 同 567. Permutation in String

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int left = 0, right = 0;
        unordered_map<char, int> window, need;

        for (const auto& ch : p) {
            ++need[ch];
        }

        int valid = 0;
        vector<int> res;

        while (right < s.size()) {
            const auto c = s[right];
            ++window[c];
            ++right;

            if (need.find(c) != need.end() && window[c] == need[c]) {
                ++valid;
            }

            while (right - left >= p.size()) {
                if (valid == need.size()) {
                    res.emplace_back(left);
                }

                const auto d = s[left];
                if (need.find(d) != need.end() && window[d] == need[d]) {
                    --valid;
                }

                --window[d];
                ++left;
            }
        }

        return res;
    }
};
  • time：$O(n1 + n2)$ ➔ n1、n2 分別為 s、p 的長度
    • $O(n1)$：s 中的每個元素最多被遍歷 2 次（left、right）
    • $O(n2)$：遍歷 p 計算 need
  • space：$O(1)$ ➔ window、need 長度皆為 $O(26)$