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
10 ай бұрын
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
10 ай бұрын
@@johndong4754 Thanks a lot for the affirmation John. I'm able to understand why the solution works.
@venkatasriharsha4227
2 жыл бұрын
After watching so many problems u solved, it's just a cake walk for me to solve this. Thanks a ton bro ❤️
@daniyaljavaid329
4 ай бұрын
was creating map for every substring when sliding a window & now using only single map for sliding, improved from 1300ms to 450ms kotlin
@chethan0
2 жыл бұрын
@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.
@vedgantilles9379
2 жыл бұрын
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
@rabomeister
6 күн бұрын
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?
@VarunMittal-viralmutant
2 жыл бұрын
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
@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
@srinadhp
2 жыл бұрын
As usual very aesthetic explanation and solution!
@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
5 ай бұрын
yes it is, shift right by len(p)
@7Ibby
2 жыл бұрын
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
2 жыл бұрын
you dont need a for loop to check if the dicts are equal
@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
7 ай бұрын
I also think like you
@isabelayala7477
2 жыл бұрын
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
2 жыл бұрын
what is logic here in 16 line can anyone explain me
@user-ff2ep5kk5i
7 ай бұрын
@@Rishabhsingh-ev7ii since we are comparing the maps, we need to pop the key when there is a 0 count for that key.
@auroshisray9140
2 жыл бұрын
Really helpful ...from approach to code is always a tough part
@ramyaarathnakumar7468
2 жыл бұрын
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
6 ай бұрын
I have the same question
@swarnabhkashyap5764
2 жыл бұрын
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
2 жыл бұрын
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
@MP-ny3ep
Жыл бұрын
This solution is awesome . Thank you so much !
@shreyabhattacherjee6388
6 ай бұрын
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
@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
@garwar1234
2 жыл бұрын
Getting time limit exceeded on leetcode for this solution. I coded in swift.
@zihaoli9683
2 жыл бұрын
wow this is pretty brilliant
@krateskim4169
Жыл бұрын
Thank You
@MyPodie
2 жыл бұрын
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!!
@kumarspandanpattanayak3489
Жыл бұрын
Thanks Man , good one :)
@sam_pnw
2 жыл бұрын
Good job
@mingjuhe1514
2 жыл бұрын
Thanks bro
@naveenprasanthsa3749
2 жыл бұрын
Happy diwali💥💣
@pratyakshsinha6292
2 жыл бұрын
Laughs in C++
@SAROJKUMAR-xe8vm
9 ай бұрын
so the time complexity will be O(len(s)*len(p)), because comparing two dictionaries will take O(len(keys))
@lilyh4573
2 жыл бұрын
Are all medium problems this tricky and hard?!? Oh man DX thanks for trying to teach us noobs Neet!!
@ngneerin
2 жыл бұрын
Can't compare two hashmaps in javascript in one sentence. It is a O(n) operation
@mocamoca_enh
2 жыл бұрын
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.
@nagendrabommireddi8437
2 жыл бұрын
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
2 жыл бұрын
Baeause u are using Counter function , Time Complexity for Counter Function is O(n)
@nagendrabommireddi8437
2 жыл бұрын
@@nagadinesh8364 thank you bro
@sagarpotnis1215
2 жыл бұрын
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?
@varunshrivastava2706
2 жыл бұрын
Just one suggestion @NeetCode please avoid using one-liners they are not readable and cause ambiguity.
@fa11en1ce
2 жыл бұрын
Looks fine to me imo
@B-Billy
5 ай бұрын
No issues in that...
@manasisingh294
7 күн бұрын
at some point, you'll have to write one-liners. It's better to start early and keep practising alongside.
@asrahussain8642
Жыл бұрын
10:44 why did we pop s[l] ?
@manasisingh294
7 күн бұрын
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.
@gladyouseen8160
2 жыл бұрын
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
2 жыл бұрын
share ur code
@parulvats
Жыл бұрын
wow
@friction5001
2 жыл бұрын
First comment
@manasisingh294
7 күн бұрын
so?
@foreverbowie2720
2 ай бұрын
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
@Rishabhsingh-ev7ii
2 жыл бұрын
what is logic here in 16 line can anyone explain me
@hero_py
2 жыл бұрын
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.
@manasisingh294
7 күн бұрын
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).
Пікірлер: 65