Find All Anagrams in a String - Leetcode 438 - Python

0:00 - Read the problem
2:30 - Drawing Explanation
6:54 - Coding Explanation

leetcode 438

#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[venkatasriharsha]

After watching so many problems u solved, it's just a cake walk for me to solve this. Thanks a ton bro ❤️

[xyz-vvtg]

Folks is there anyone like me who first sees the question, thinks a lot about it and have absolutely no idea how to even approach the problem, and then later checks neetcode just see the solution?
I'm afraid that I can't even think of solutions to basic problems

[daniyaljavaid]

was creating map for every substring when sliding a window & now using only single map for sliding, improved from 1300ms to 450ms kotlin

[chethan]

@Neetcode : I think you should increment the left pointer only after appending it to the result if the counts match, Otherwise you will be appending the index+1 into the results

[srinadhp]

As usual very aesthetic explanation and solution!

[Ibby]

Hi. Really enjoy your videos and have been learning a lot from you. Just wanted to share my way I did this problem, if that's cool.
After checking the edge case of length of p being greater than length of s, I created two dictionaries/hashmaps and initialized them with all the letters from set(s+p) with 0. This allows you to skip the check if the letter in the dictionary/hashmap is zero and pop it. Then incremented the first (length of p) letters in both dictionaries/hashmaps. After, I just use a for loop, check if the dictionaries are equal and then decrement the left letter and increment the next letter in string s until the end.
I'd share my code if you're cool with it or if you're interested.

[vedgantilles]

If the size of alphabet not a constant, this solution has O(n^2) asymptotic in worst case.
Actually, there is O(n) solution in this case.
You should calculate the number of symbols, which counts in p equal to counts in current window
And when this number will be equal to number of keys in pCount, it's the answer

[VarunMittal-viralmutant]

Using deque, islice and Counter :)

p_c = Counter(p)
anagrams = []
it = iter(s)
sliding_window = deque(islice(it, len(p)), maxlen=len(p))

s_c = Counter(sliding_window)

if s_c == p_c:
anagrams.append(0)

for index, char in enumerate(it, start=1):
s_c[char] += 1
s_c[s[index-1]] -= 1
if s_c == p_c:
anagrams.append(index)
return anagrams

[fayequehannan]

There can be also one more optimisation we can do if we found a char which is not present in p then we can simply move the left pointer to the position of that char in s +1 and apply the same algo from there...please let me know if it can be considered as a optimisation or not

[viggicodes]

One more approach using char counter -> represent the string as count of each alphabet.

def findAnagrams(self, s: str, p: str) -> List[int]:
l = 0
res = []
counter = [0] *26

for c in p:
index = ord(c) - ord('a')
counter[index] = counter[index] + 1

counter2 = [0] * 26
for r in range(len(s)):

index = ord(s[r]) - ord('a')
counter2[index] = counter2[index] + 1


while r - l + 1 == len(p):
if counter2 == counter:
res.append(l)
index = ord(s[l]) - ord('a')
counter2[index] = counter2[index] -1
l = l + 1



return res

[shreyabhattacherjee]

Thanks a lot for the solution, this is very helpful, how is it ensured that the keys in the two hash maps are in the same order ? If they are not the same then the comparison of the two dictionaries will result in False

[MP-nyep]

This solution is awesome . Thank you so much !

[auroshisray]

Really helpful ...from approach to code is always a tough part

[isabelayala]

This makes so much sense. I had a similar approach in mind but just couldn’t figure out how to implement it. Thanks so much!

[Chirayu]

Another similar approach:
Create two pointers L and R
Check both the maps:
If you find any freq lesser than the other map-> Increment R
If you find any freq greater than the other map-> Increment L
If all are eqaul -> Updater answer and increment both L and R

[swarnabhkashyap]

Great video. Just one doubt. Why are we decrementing the count of the character represented by the left pointer by 1 instead of removing the character from sCount dictionary?

[ramyaarathnakumar]

Have a doubt here, if we're anyways creating a hashmap sliding window over s, why not start from 0, the operation is anyway the same, why do we need to create a separate for loop initially?

[garwar]

Getting time limit exceeded on leetcode for this solution. I coded in swift.

[MyPodie]

Is there a way to solve it with just one for loop? Or is the first loop necessary and why is that? I keep trying to come up with one but can't. Thanks!!

[SAROJKUMAR-xevm]

so the time complexity will be O(len(s)*len(p)), because comparing two dictionaries will take O(len(keys))