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?
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
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
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
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?
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!!
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.
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.
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))
Wait up, how is this O(n*k) even with any character? If it's the same leetcode question, I always thought it's just O(N_source) because comparison is always fixed at 26 key-value pairs, so O(1). So if it's any character, you can do the same thing just with 256 characters - key value pairs, but that's still O(1). That time doesn't vary if you have a super long p string input no? Your dictionary size doesn't change when you have short or long input strings. The comparison is still just 256 comparisons, which is O(1). So why isn't that not enough? You can also do array method but it's the same.
@ yes, you absolutely right. I’ve said to them about dictionary size and etc, but they said that it’s not optimal solution, because target and source strings are Unicode, not ASCII
@@doudmitryAh that makes sense, Unicode is way too big even if its constant. It's like 150k. I researched this one hard and actually found the optimal way which is true O(n). They have this matchCount way of solving this question, where you only track how many characters have exactly the right frequency you need (via matchCount++/--) instead of comparing entire dictionaries. When matchCount equals the number of unique chars in target string, you found an anagram. Each operation is O(1), making the whole solution O(n) regardless of character set! Let me know if that understanding is correct. I personally think this is basically impossible to come up with in an interview unless you've practiced it this way before...What company is that?
@@doudmitry class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: if len(s) < len(p): return []
need = defaultdict(int) for c in p: need[c] += 1
window = defaultdict(int) matchCount = 0 result = [] left = 0
for right in range(len(s)): # Add right char window[s[right]] += 1 if s[right] in need: if window[s[right]] == need[s[right]]: matchCount += 1 elif window[s[right]] == need[s[right]] + 1: matchCount -= 1
# Remove left char when window too big if right - left + 1 > len(p): window[s[left]] -= 1 if s[left] in need: if window[s[left]] == need[s[left]]: matchCount += 1 elif window[s[left]] == need[s[left]] - 1: matchCount -= 1 left += 1
# Check for anagram when window is right size if right - left + 1 == len(p): if matchCount == len(need): result.append(left)
@ yes, your solution seems correct. But I’ve found the solution when you do the same, but instead of using counter - you check is dictionary empty. The company is “yandex”
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.
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
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
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?
@@shinoz9517 mf gave up
After watching so many problems u solved, it's just a cake walk for me to solve this. Thanks a ton bro ❤️
@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
As usual very aesthetic explanation and solution!
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
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?
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
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
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)
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
This solution is awesome . Thank you so much !
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
Really helpful ...from approach to code is always a tough part
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 Man , good one :)
wow this is pretty brilliant
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!!
Thank You
Getting time limit exceeded on leetcode for this solution. I coded in swift.
Got this question in Microsoft interview
Good job
Thanks 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.
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.
Happy diwali💥💣
Are all medium problems this tricky and hard?!? Oh man DX thanks for trying to teach us noobs Neet!!
so the time complexity will be O(len(s)*len(p)), because comparing two dictionaries will take O(len(keys))
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
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?
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))
Wait up, how is this O(n*k) even with any character? If it's the same leetcode question, I always thought it's just O(N_source) because comparison is always fixed at 26 key-value pairs, so O(1). So if it's any character, you can do the same thing just with 256 characters - key value pairs, but that's still O(1). That time doesn't vary if you have a super long p string input no? Your dictionary size doesn't change when you have short or long input strings. The comparison is still just 256 comparisons, which is O(1). So why isn't that not enough? You can also do array method but it's the same.
@ yes, you absolutely right. I’ve said to them about dictionary size and etc, but they said that it’s not optimal solution, because target and source strings are Unicode, not ASCII
@@doudmitryAh that makes sense, Unicode is way too big even if its constant. It's like 150k. I researched this one hard and actually found the optimal way which is true O(n). They have this matchCount way of solving this question, where you only track how many characters have exactly the right frequency you need (via matchCount++/--) instead of comparing entire dictionaries. When matchCount equals the number of unique chars in target string, you found an anagram. Each operation is O(1), making the whole solution O(n) regardless of character set! Let me know if that understanding is correct. I personally think this is basically impossible to come up with in an interview unless you've practiced it this way before...What company is that?
@@doudmitry
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
if len(s) < len(p):
return []
need = defaultdict(int)
for c in p:
need[c] += 1
window = defaultdict(int)
matchCount = 0
result = []
left = 0
for right in range(len(s)):
# Add right char
window[s[right]] += 1
if s[right] in need:
if window[s[right]] == need[s[right]]:
matchCount += 1
elif window[s[right]] == need[s[right]] + 1:
matchCount -= 1
# Remove left char when window too big
if right - left + 1 > len(p):
window[s[left]] -= 1
if s[left] in need:
if window[s[left]] == need[s[left]]:
matchCount += 1
elif window[s[left]] == need[s[left]] - 1:
matchCount -= 1
left += 1
# Check for anagram when window is right size
if right - left + 1 == len(p):
if matchCount == len(need):
result.append(left)
return result
@ yes, your solution seems correct. But I’ve found the solution when you do the same, but instead of using counter - you check is dictionary empty. The company is “yandex”
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.
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
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
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).
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?
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