Find All Anagrams in a String

https://leetcode.com/problems/find-all-anagrams-in-a-string/description/

Given a stringsand anon-emptystringp, find all the start indices ofp's anagrams ins.

Strings consists of lowercase English letters only and the length of both stringssandpwill not be larger than 20,100.

The order of output does not matter.

Thoughts

找出所有p的permutation在s中出现的起始位置。维持p大小的静态窗口在s中前移，检查窗口是否是p的permutation。检查是否permutation可以维持一个freq map，当字符对应的值为负数表欠缺，正数表超出，0时刚好。cnt记录窗口内能用作p的permutation的字符数，当r扩张时，检查之前freq[r]是否在欠缺状态，是的话cnt++；在剔除l时，同理检查freq[l]是否在欠缺状态或刚好的状态，是的话cnt--；当cnt == p.len说明窗口内所有元素都用作了permutation，即一个所找结果。

Code

/*
 * @lc app=leetcode id=438 lang=cpp
 *
 * [438] Find All Anagrams in a String
 */

// @lc code=start
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        if (s.length() < p.length()) return res;
        vector<int> freq(26, 0);
        int l = 0, r = 0, cnt = 0, N = p.length();
        for (const auto c : p) --freq[c - 'a']; 
        for (; r < N; ++r) {
            const auto k = s[r] - 'a';
            if (freq[k] < 0) ++cnt;
            ++freq[k];
        }
        if (cnt == N) res.push_back(l);
        while (r < s.length()) {
            const auto k = s[r] - 'a', l = s[r - N] - 'a';
            if (freq[k] < 0) ++cnt;
            ++freq[k];
            if (freq[l] <= 0) --cnt;
            --freq[l];
            if (cnt == N) res.push_back(r - N + 1);
            ++r;
        }
        return res;
    }
};
// @lc code=end

Analysis

时间复杂度O(n).