from collections import Counter


class Solution(object):
	def findAnagrams(self, s, p):
		"""
		给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
		字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
		说明：
		字母异位词指字母相同，但排列不同的字符串。
		不考虑答案输出的顺序。
		---
		示例 1:
		输入:
		s: "cbaebabacd" p: "abc"
		输出:
		[0, 6]
		解释:
		起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
		起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
		---
		输入:
		s: "abab" p: "ab"
		输出:
		[0, 1, 2]
		解释:
		起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
		起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
		起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
		:type s: str
		:type p: str
		:rtype: List[int]
		"""
		np = len(p)
		ns = len(s)
		lookup = Counter(p)
		s_dict = Counter(s[:np-1])
		res = []
		for i in range(np-1,ns):
			s_dict[s[i]] += 1
			if s_dict == lookup:
				res.append(i-np+1)
			s_dict[s[i-np+1]] -= 1
			if s_dict[s[i-np+1]] == 0:
				s_dict.pop(s[i-np+1])

		return res
a = Solution()
# print(a.findAnagrams( "cbaebabacd" ,"abc"))
print(a.findAnagrams("abab" ,"ab"))

