<p>Given two strings <code>s</code> and <code>p</code>, return <em>an array of all the start indices of </em><code>p</code><em>&#39;s anagrams in </em><code>s</code>. You may return the answer in <strong>any order</strong>.</p>

<p>An <strong>Anagram</strong> is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cbaebabacd&quot;, p = &quot;abc&quot;
<strong>Output:</strong> [0,6]
<strong>Explanation:</strong>
The substring with start index = 0 is &quot;cba&quot;, which is an anagram of &quot;abc&quot;.
The substring with start index = 6 is &quot;bac&quot;, which is an anagram of &quot;abc&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abab&quot;, p = &quot;ab&quot;
<strong>Output:</strong> [0,1,2]
<strong>Explanation:</strong>
The substring with start index = 0 is &quot;ab&quot;, which is an anagram of &quot;ab&quot;.
The substring with start index = 1 is &quot;ba&quot;, which is an anagram of &quot;ab&quot;.
The substring with start index = 2 is &quot;ab&quot;, which is an anagram of &quot;ab&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length, p.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>s</code> and <code>p</code> consist of lowercase English letters.</li>
</ul>

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        std::vector<int> results;
        std::map<char, int> p_count;
        for (int i = 0; i < p.length(); ++i) {
            const char cur = p[i];
            UpdateOrInsert(cur, p_count);
        }

        std::map<char, int> sub_count;
        int right = 0, left = 0;
        int valid_num = 0;

        const auto is_invalid = [p_count](const char cur) {
            return p_count.find(cur) == p_count.end();
        };
        const auto count_matches = [&p_count, &sub_count](const char& cur) {
            return p_count.find(cur) != p_count.end() &&
                   sub_count.find(cur) != sub_count.end() &&
                   p_count[cur] == sub_count[cur];
        };
        while (right < s.length()) {
            const char r_char = s[right];
            if (is_invalid(r_char)) {
                right++;
                left = right;
                sub_count.clear();
                valid_num = 0;
                continue;
            }
            // left == right, substring is [left, right)
            UpdateOrInsert(r_char, sub_count);
            right++;
            if (count_matches(r_char)) {
                valid_num++;
            }
            while (left < right && sub_count[r_char] > p_count[r_char]) {
                const char l_char = s[left];
                if (count_matches(l_char)) {
                    valid_num--;
                }
                sub_count[l_char]--;
                left++;
            }
            if (valid_num == p_count.size()) {
                results.emplace_back(left);
            }
        }
        return results;
    }

    std::map<char, int>::iterator UpdateOrInsert(const char& c,
                                                 std::map<char, int>& count) {
        auto it = count.find(c);
        if (it == count.end()) {
            auto emplace_result = count.emplace(c, 0);
            return emplace_result.first;
        }
        it->second++;
        return it;
    }
};
16791