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
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
@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
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.
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
Keys? you can get aab = bba if you care about keys. what you say is a first constraint, then you need to count them all too. is there anything i misunderstood?
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
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
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
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
Ah! Why did I not think of this ? I think if i had tried solving this problem on my own without the motive of trying to master the sliding window algorithm, I would have come up with simlar solution.
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?
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
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
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?
Failed interview with this solution. On the real interview target and source strings were containing any characters, so complexity of this solution became O(n*k) which was not enough))
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!!
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.
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
we gotta slide our window and for that you basically pop one from the left end and start considering one more from the right end. And that popping is done when you aren't considering that letter at the moment (it is not in your current window). 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.
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.
we gotta slide our window and for that you basically pop one from the left end and start considering one more from the right end. And that popping is done when you aren't considering that letter at the moment (it is not in your current window).
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
After watching so many problems u solved, it's just a cake walk for me to solve this. Thanks a ton bro ❤️
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
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
@@johndong4754 Thanks a lot for the affirmation John. I'm able to understand why the solution works.
What's your status now? Have you improved?
@@shinoz9517 mf gave up
@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
Nope, check the algorithm ,its absolutely fine...make a dry run ,u will get it.
was creating map for every substring when sliding a window & now using only single map for sliding, improved from 1300ms to 450ms kotlin
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.
you dont need a for loop to check if the dicts are equal
As usual very aesthetic explanation and solution!
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
Keys? you can get aab = bba if you care about keys. what you say is a first constraint, then you need to count them all too. is there anything i misunderstood?
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
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
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
yes it is, shift right by len(p)
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!
what is logic here in 16 line can anyone explain me
@@Rishabhsingh-ev7ii since we are comparing the maps, we need to pop the key when there is a 0 count for that key.
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
I also think like you
This solution is awesome . Thank you so much !
Really helpful ...from approach to code is always a tough part
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
Ah! Why did I not think of this ? I think if i had tried solving this problem on my own without the motive of trying to master the sliding window algorithm, I would have come up with simlar solution.
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?
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
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
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?
I have the same question
Failed interview with this solution. On the real interview target and source strings were containing any characters, so complexity of this solution became O(n*k) which was not enough))
Thanks Man , good one :)
wow this is pretty brilliant
Getting time limit exceeded on leetcode for this solution. I coded in swift.
Thank You
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!!
so the time complexity will be O(len(s)*len(p)), because comparing two dictionaries will take O(len(keys))
Are all medium problems this tricky and hard?!? Oh man DX thanks for trying to teach us noobs Neet!!
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
a=Counter(list(p))
print(a)
d=[]
i=0
j=0
while j
Baeause u are using Counter function , Time Complexity for Counter Function is O(n)
@@nagadinesh8364 thank you bro
Thanks bro
Can't compare two hashmaps in javascript in one sentence. It is a O(n) operation
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.
Good job
how is the complexity of the solution O(n) ? should it be O(s x p)
The size of the hashmap is at max O(26). Therefore it is O(p + s * 26)
Me too, the dict comparison should take O(p) right?
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
share ur code
Happy diwali💥💣
10:44 why did we pop s[l] ?
we gotta slide our window and for that you basically pop one from the left end and start considering one more from the right end. And that popping is done when you aren't considering that letter at the moment (it is not in your current window). 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.
Laughs in C++
what is logic here in 16 line can anyone explain me
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.
we gotta slide our window and for that you basically pop one from the left end and start considering one more from the right end. And that popping is done when you aren't considering that letter at the moment (it is not in your current window).
Just one suggestion @NeetCode please avoid using one-liners they are not readable and cause ambiguity.
Looks fine to me imo
No issues in that...
at some point, you'll have to write one-liners. It's better to start early and keep practising alongside.
If it's a simple statement or a ternary, don't see a problem, if the operation does 2 or 3 things I would consider it a problem
I used to be a noob 2 years ago 😂😂. Looking back at my old comments is like a trip down the memory lane. Thanks for commenting tho
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
wow
First comment
so?