给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

• 字母异位词指字母相同，但排列不同的字符串。
• 不考虑答案输出的顺序。

示例 1:

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2:

输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

Solution

• 滑动窗口算法

参考 滑动窗口技巧 的思路

# @lc code=start
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        left, right = 0, 0
        res = []
        
        window = collections.defaultdict(int)
        needs = collections.defaultdict(int)
        for char in p:
            needs[char] += 1

        match = 0
        while(right < len(s)):
            c1 = s[right]
            if c1 in needs:
                window[c1] += 1
                if window[c1] == needs[c1]:
                    match += 1
            right += 1
            
            while match==len(needs):
                if right-left == len(p):
                    res.append(left)
                c2 = s[left]
                if c2 in needs:
                    window[c2] -= 1
                    if window[c2] < needs[c2]:
                        match -= 1
                left += 1
        
        return res
# @lc code=end

cpp

参考 @qtaro

用一个滑动窗口盖在数组s上，右边界一位一位向右滑动并标记访问到的字符，滑动窗口拓展到p那么长时，当前滑动窗口覆盖的子串是一个可能解。于是直接比较s和p的哈希表是否相等（c++的vector可以直接用==比较）。如果相等，ans里推入当前左边界值l；否则，左边界右移一位并删除曾经访问的字符的标记。进入下一轮循环。循环结束的条件是右边界在循环体内滑动到lenS-1，下一轮循环判断就会终止循环。

两个优化点：左边界最小取值是0，可能解的长度是lenP，所以右边界最小取值是lenP-1，所以r < lenP-1直接continue；p比s短立刻返回无解。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        if(s.size()< p.size())
            return res;
        vector<int> needs(256, 0);
        vector<int> window(256, 0);
        for(char c : p)
            ++needs[c];

        int l=0, r=-1; // 滑动窗口初始化为不存在区间 [0, -1]
        while(l<s.size()){
            if(r+1 < s.size()) // 窗口右边界右移一位 并标记访问到的值
                ++window[s[++r]];
            if(r < p.size()-1)
                continue;
            if(needs == window)
                res.push_back(l);
            --window[s[l++]]; // 窗口左边界右移一位 并删除曾经访问的值的标记
        }        
        return res;
    }
};