Find All Anagrams in a String
Intuition
Solution
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
if len(s) < len(p):
return []
counts = {c:p.count(c) for c in string.ascii_lowercase if c in p}
for c in s[:len(p) - 1]:
if c in counts:
counts[c] -= 1
if counts[c] == 0:
counts.pop(c)
else:
counts[c] = -1
ans = []
for i in range(len(s) - len(p) + 1):
c = s[i + len(p) - 1]
if c in counts:
counts[c] -= 1
if counts[c] == 0:
counts.pop(c)
else:
counts[c] = -1
if not counts:
ans.append(i)
c = s[i]
if c in counts:
counts[c] += 1
if counts[c] == 0:
counts.pop(c)
else:
counts[c] = 1
return ans