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
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
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
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.
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?
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
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
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
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!!
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
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.
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.
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 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
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?
After watching so many problems u solved, it's just a cake walk for me to solve this. Thanks a ton bro ❤️
was creating map for every substring when sliding a window & now using only single map for sliding, improved from 1300ms to 450ms kotlin
@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.
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)
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
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!
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.
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
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
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
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
This solution is awesome . Thank you so much !
Really helpful ...from approach to code is always a tough part
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!!
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
Getting time limit exceeded on leetcode for this solution. I coded in swift.
wow this is pretty brilliant
Thank You
Thanks Man , good one :)
Good job
Thanks bro
so the time complexity will be O(len(s)*len(p)), because comparing two dictionaries will take O(len(keys))
Happy diwali💥💣
Are all medium problems this tricky and hard?!? Oh man DX thanks for trying to teach us noobs Neet!!
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.
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?
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
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++
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
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
wow
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).
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
First comment
so?