Find All Anagrams in a String - Leetcode 438 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/find-al...
0:00 - Read the problem
2:30 - Drawing Explanation
6:54 - Coding Explanation
leetcode 438
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@venkatasriharsha4227]

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

[@srinadhp]

As usual very aesthetic explanation and solution!

[@auroshisray9140]

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

[@MP-ny3ep]

This solution is awesome . Thank you so much !

[@7Ibby]

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.

[@EagerEggplant]

you dont need a for loop to check if the dicts are equal

[@chethan0]

@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

[@pritz9]

Nope, check the algorithm ,its absolutely fine...make a dry run ,u will get it.

[@kumarspandanpattanayak3489]

Thanks Man , good one :)

[@vedgantilles9379]

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

[@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!!

[@zihaoli9683]

wow this is pretty brilliant

[@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

[@sam_pnw]

Good job

[@garwar1234]

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

[@krateskim4169]

Thank You

[@mingjuhe1514]

Thanks bro

[@fayequehannan2473]

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

[@Bullimicporkupine]

yes it is, shift right by len(p)

[@isabelayala7477]

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!

[@Rishabhsingh-ev7ii]

what is logic here in 16 line can anyone explain me

[@user-ff2ep5kk5i]

@@Rishabhsingh-ev7ii since we are comparing the maps, we need to pop the key when there is a 0 count for that key.

[@xyz-vv5tg]

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

[@johndong4754]

Absolutely nothing wrong with that! It's better to check the solution than to spend too much time trying to solve it on your own. Just make sure you understand why the solution works and how to come up with it

[@xyz-vv5tg]

@@johndong4754 Thanks a lot for the affirmation John. I'm able to understand why the solution works.

[@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

[@daniyaljavaid329]

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

[@shreyabhattacherjee6388]

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

[@ramyaarathnakumar7468]

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?

[@shreyabhattacherjee6388]

I have the same question

[@swarnabhkashyap5764]

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?

[@rajkumarkhatri8119]

Think of ‘aaaaaaa’ if your left pointer is at first ‘a’ then left += 1, if you remove ‘a’ from count dictionary, that is misleading because you several other occurrences of ‘a’ in your sliding window

[@naveenprasanthsa3749]

Happy diwali💥💣

[@Chirayu19]

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

[@Witch_Quiz]

I also think like you

[@lilyh4573]

Are all medium problems this tricky and hard?!? Oh man DX thanks for trying to teach us noobs Neet!!

[@asrahussain8642]

10:44 why did we pop s[l] ?

[@SAROJKUMAR-xe8vm]

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

[@ngneerin]

Can't compare two hashmaps in javascript in one sentence. It is a O(n) operation

[@mocamoca_enh]

It is also O(n) in Python. He explains that comparing the 2 hashmaps in this specific problem to be O(26) since there are constraints on the anagram string to be only using a-z. Despite the size of string p either hashmap will have a maximum size of 26.

[@sagarpotnis1215]

how is the complexity of the solution O(n) ? should it be O(s x p)

[@nioi]

The size of the hashmap is at max O(26). Therefore it is O(p + s * 26)

[@xenky0]

Me too, the dict comparison should take O(p) right?

[@faizanahmed6072]

def findAnagrams(self, s: str, p: str) -> List[int]: if len(s) < len(p): return [] c=Counter(p) res=[] for i in range(len(s)-len(p)+1): temp=Counter(s[i:i+len(p)]) if temp==c: res.append(i) return res

[@Rishabhsingh-ev7ii]

what is logic here in 16 line can anyone explain me

[@hero_py]

We increment the left pointer. As such, we are no longer pointing at a character (and we're pointing at a new character at the left pointer), so we decrement the count of that character in sCount. If the count of that character is 0, we remove it from the dictionary.

[@gladyouseen8160]

Hey bro i follow your videos. The most of videos are pythonic way. It would be good if you tell some logic that can be possible to optmise more. For e.g. Here we could have reduced one dictionary and use a variable called "distinct_letters_in_d" and when ever it reaches to 0 we could have added the "l" to res

[@ritwik121]

share ur code

[@nagendrabommireddi8437]

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: a=Counter(list(p)) print(a) d=[] i=0 j=0 while j

[@nagadinesh8364]

Baeause u are using Counter function , Time Complexity for Counter Function is O(n)

[@nagendrabommireddi8437]

@@nagadinesh8364 thank you bro

[@pratyakshsinha6292]

Laughs in C++

[@parulvats]

wow

[@friction5001]

First comment

[@foreverbowie2720]

Share my super simple solution: def findAnagrams(self, s: str, p: str) -> List[int]: res = [] p = sorted(p) l = 0 for r in range(len(p) - 1, len(s)): if sorted(s[l:r + 1]) == p: res.append(l) l += 1 return res

[@varunshrivastava2706]

Just one suggestion @NeetCode please avoid using one-liners they are not readable and cause ambiguity.

[@fa11en1ce]

Looks fine to me imo

[@B-Billy]

No issues in that...