"""
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
"""
from collections import Counter
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        rt = []
        pdict = {}
        if len(p) > len(s):
            return rt
        for var in p:
            pdict[var] = pdict.setdefault(var, 0) + 1
        counter = len(pdict)
        begin = end = 0
        while(end < len(s)):
            var = s[end]
            if var in pdict:
                pdict[var] -= 1
                if pdict[var] ==0:
                    counter -=1
            end += 1
            while counter==0:
                var = s[begin]
                if var in pdict:
                    pdict[var] += 1
                    if pdict[var] > 0:
                        counter +=1
                if end-begin == len(p):
                    rt.append(begin)
                begin +=1
        return rt