Find All Anagrams in a String | Sliding Windows

# Desciption

Given two strings s and p, return an array of all the start indices of p\'s anagrams in s. You may return the answer in any order.

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

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".

sliding windows

# Code

• submit code
``````class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
# Creat a NeedDict5
need_dict = {}
for m in p:
need_dict[m] = need_dict.get(m,0) + 1

left = 0
right = 0
valid = 0

window_dict = {}

result = []

tmp = ""

while left < len(s):
INPUT = s[left]
left += 1

tmp += INPUT

window_dict[INPUT] = window_dict.get(INPUT,0) + 1

if(need_dict.get(INPUT)):
if(need_dict.get(INPUT) == window_dict.get(INPUT,0)):
valid += 1

while valid == len(need_dict) and right < len(s):
OUTPUT = s[right]
right += 1

if(len(tmp) == len(p)):
result.append(right - 1)

tmp = tmp[1:]

window_dict[OUTPUT] = window_dict.get(OUTPUT) - 1

if(need_dict.get(OUTPUT,0) > window_dict.get(OUTPUT,0) and need_dict.get(OUTPUT) != 0):
valid -= 1

return result

``````
• full code
``````class Solution:
def findAnagrams(self, s: str, p: str):

result = []

need_dict = {}
for i in p:
need_dict[i] = need_dict.get(i,0) + 1

right = 0
left = 0
valid = 0

wind_dict = {}

tmp = ""

while left < len(s):
In = s[left]
left += 1
tmp += In
print("1_tmp:\t" + tmp)
wind_dict[In] = wind_dict.get(In, 0) + 1

if(need_dict.get(In)):
if(need_dict.get(In) == wind_dict.get(In)):
valid += 1

while valid == len(need_dict) and right < len(s):
print("-------------before desec----------------")
print("valid:\t" + str(valid))
print("tmp\t" + tmp)
print("###############################")
OUT = s[right]
right += 1

if(len(tmp) == len(p)):
result.append(right - 1)

tmp = tmp[1:]
wind_dict[OUT] = wind_dict.get(OUT, 0) - 1

if(need_dict.get(OUT,0) > wind_dict.get(OUT,0) and need_dict.get(OUT) != 0):
print("window:\t" + str(wind_dict))
print("desec_tmp:\t" + tmp)
valid -= 1

return result

S = Solution()
# s = "abc"
# p = "abc"
# s = "abacbabc"
# p = "abc"

s = "cbaebabacd"
p = "abc"

print(S.findAnagrams(s,p))
``````

# 👇 Share | 分享 👇

### 要不赞赏一下?  微信  支付宝  PayPal  Bitcoin

``https://www.emperinter.info/2022/02/26/find-all-anagrams-in-a-string/``

## My Github Contributions 