Code on Github: github.com/neetcode-gh/leetcode/blob/main/28-Implement-strStr.py I recommend using the timestamps and watching this at 1.5x Speed, at least the LPS portion, which turned out longer than I expected.
@@ary_21 because this will only return the first occurence of the substring. Morever, the "substring" function internelly works in O(n) time. So the totall complexity would be O(n^2), where the optimal approch has O(n) time. And that's very bad. And also if you want to count the number of occurences of the substring, the "stl function" approach will definitely give you TLE. :)
Thank you for acknowledging how complex this algo is. I thought i was crazy for struggling so much. Finally understand it, somewhat :'). Thanks for making this
lmao, as soon as I submitted his first solution (m * n) doing it myself and it exceeded time I realized this wasn't going to be an "easy" problem :') . WTH is this leetcode.
@@WoWkiddymage To be honest trying the same problem with rabin karps algorithm is very easy. If given the hint "each sliding window can have a unique signature" you can yourself re-discover the algo even if not read of before. Kmp , booyre moore , rabin karp are all linear algorithms
@@WoWkiddymage well I wrote a brute force (mentioned below, which got accepted btw) but the code was so ugly, I knew for sure there exists an optimal solution and here I am. bool rotateString(string s, string goal) { int n = s.size(); for(int i=0; i
I wish this video came around sooner. Was asked a similar question during a Microsoft interview two weeks ago. The interviewer expected me to come up or remember KMP lol. But thank you NC! Please keep up the good works!
Please try to make future solution videos in this dual screen format. It’s really helpful to visualize the intuition behind each line of code in real time.
This is really a great attempt at trying to explain the KMP and somewhat some intuition behind why it works! Really a very complicated and non-intuitive algorithm but brilliantly explained here.
One of the greatest explanations Neel. It's really very helpful and let me tell you I have seen it more than 4 times and now I know how it works. Thanks, man.
This is the best explaination video for KMP algorithm!! I find that explaining code parallely is very helpful for this algorithm. Thank you for your efforts!!
Awesome work, ! thank u for putting in so much effort and thanks to me also for making 1/5th effort to make it to the end of this video. good to see that u covered so many test cases, which made the explanation more clear.
@NeetCode Please correct me if I'm wrong, but on 19:12, when you say "that's what the 1 tells us..", i think you meant to circle the 1st and the 2nd "A" in the text and not the 1st and 3rd "A".
Thanks NeetCode, it's pretty hard to find a good explanation on the KMP algorithm and you did a great job of explaining it here. Would it be possible for you to cover the Aho Corasick algorithm at some point? I'm finding it difficult to find a good resource explaining that one and having a NeetCode explained version would be a nice follow up to this one as I believe Aho Corasick uses KMP to efficiently find substrings in strings along with Tries.
I do not understand the tricky part when building the LPS array, when i and j do not match, why move j by the VPS[i - 1]? Because move that way you will skip some middle elements. Is there a proof that garentee the longest prefix suffix?
The problem with this explanation is while building the needle array, when we have needle[i] == needle[prevLPS], we set the value, lps[i] = prevLPS + 1 but you keep saying we are incrementing the value by 1 of prevLPS index value in lps array whereas we are setting the incremented value of prevLPS and not the index value of it i.e. lps[i] = prevLPS + 1 and NOT lps[i] = lps[prevLPS] + 1 Coincidentally the examples choosen had the same index value and the value inside lps array i.e. value at index 1 is 1 and value at index 2 is 2 that's why i think the choice of example was poor. Other than that the explanation was great.
hey Neetcode at timestamp 22:40, why was LPS[6]!= 6? because for the substring 'AAACAAA' -> prefix(AAACAA)==suffix('AAACAA') and that length is 6. please tell me if i am mistaken.
Hey guys, I have a question regarding the calculation of the LPS array. When it comes to the "else" condition, why do we let prevLPS = LPS[prevLPS-1] instead of decrementing prevLPS by 1? 🤔 THANKS.
24:10 I wonder why here we can say LPS[2]'s value means the first two chars match the 5th,6th chars. In my view when the LPS[2] is determined, we don't know the following matches, so its value can only tell the first two match the 1th,2th two (matching prefix-suffix numbers up to current bit). Since then LPS[2] haven't change, why has the meaning changed? Thank you the same.
Hi! I'm still relatively new to DSA so would appreciate if anyone can guide me with my question? I am confused as to why we need to work with KMP algorithm when we can directly use the indexOf() method to check if pattern exists in the String. I agree and understand that indexOf() itself might have some underlying algorithm that gets the work done for us. Do we learn this for scenarios where we can't use pre-defined methods and need to write our own code?
I was like after checking out what others solutions made by other users beats mine after I just spent my whole day learning this algorithm, and guess what? THIS: class Solution: def strStr(self,haystack: str,needle:str)->int: if needle in haystack: return haystack.index(needle) else: return-1
Probably because list.index implements this algorithm (or similar) but in C rather than Python. Side note: Since list.index throws a ValueError if the substring isn't found, it's probably better to do this as a try-except block rather than checking if the substring exists then finding it.
Now I finally understood why all my Computer Science peers in uni always told me "Knuth's algos are pure SUFFERING" XD Thanks for this very nice explanation, man! Like :+1:
at 24:28 you said that that we would take lps[prevLPS] and add 1 to it but in the code in first condition you wrote lps[i]=prevLPS+1 and not lps[prevLPS] +1
bro i got google screening interview in few days - i remember u said in one of the videos that you can find the screening question online, but i dont see it. although i have prepared from leetcode. But i remember u said the question are easy, it not that easy also, its all good medium level problems
Code on Github: github.com/neetcode-gh/leetcode/blob/main/28-Implement-strStr.py
I recommend using the timestamps and watching this at 1.5x Speed, at least the LPS portion, which turned out longer than I expected.
no that was perfect for guys like me thank you very much
Why cant we use in built stl function
String.find(substring)
To locate the index of string ?
@@ary_21 because this will only return the first occurence of the substring. Morever, the "substring" function internelly works in O(n) time. So the totall complexity would be O(n^2), where the optimal approch has O(n) time. And that's very bad. And also if you want to count the number of occurences of the substring, the "stl function" approach will definitely give you TLE. :)
@@xerOnn35
Got it 👍
Thanks !
If someone says they can explain KMP better, they are lying. It doesn't get any better than what you just did. Amazing Neetcode. 🙏
Thank you for acknowledging how complex this algo is. I thought i was crazy for struggling so much. Finally understand it, somewhat :'). Thanks for making this
exactly. i came back after leaving this algo and did not understand what I wrote at all and I thought I was just being stupid lol
0:35 - Yes, I too would describe independently re-discovering a complex search algorithm during an interview as "very very hard"
lmao, as soon as I submitted his first solution (m * n) doing it myself and it exceeded time I realized this wasn't going to be an "easy" problem :') . WTH is this leetcode.
@@WoWkiddymage
To be honest trying the same problem with rabin karps algorithm is very easy.
If given the hint "each sliding window can have a unique signature" you can yourself re-discover the algo even if not read of before.
Kmp , booyre moore , rabin karp are all linear algorithms
Especially considering it took 3 guys to initially discover it!
@@WoWkiddymage well I wrote a brute force (mentioned below, which got accepted btw) but the code was so ugly, I knew for sure there exists an optimal solution and here I am.
bool rotateString(string s, string goal) {
int n = s.size();
for(int i=0; i
I saw many explanations on kmp algo, but the explanation you provided is the best and the easiest to understand, kudos to you !
I wish this video came around sooner. Was asked a similar question during a Microsoft interview two weeks ago. The interviewer expected me to come up or remember KMP lol. But thank you NC! Please keep up the good works!
The best online KMP algorithm explanation! Thank you Sir!
Please try to make future solution videos in this dual screen format. It’s really helpful to visualize the intuition behind each line of code in real time.
Yeah
We asked for it in the previous video and you made a video on it, thanks!
Exactly, I literally put a comment on his last video. What a legend
Beautiful explanation, only the one who understands the logic can explain others with such clarity
At 22:00 I think I really started getting it!
Thanks Neetcode for the clear explanations as usual.
This is really a great attempt at trying to explain the KMP and somewhat some intuition behind why it works! Really a very complicated and non-intuitive algorithm but brilliantly explained here.
One of the best explanation out there for this hard hard hard algorithm
Thanks Mr.Neet for listening.
why do u sound like you're explaining it to me for the fifth time
This is the best KMP solution I've been seen, very clear, thank you!
One of the greatest explanations Neel. It's really very helpful and let me tell you I have seen it more than 4 times and now I know how it works. Thanks, man.
Wow. You listened to the feedback from viewers. Goddamn legend ✌
Thank you for your hard work ! Video is incredibly useful and easy to understand.
This is the best explaination video for KMP algorithm!! I find that explaining code parallely is very helpful for this algorithm. Thank you for your efforts!!
You saying again and again it's tough and really it's. But you make the algorithm very easy by your explanation. Superb work....
Awesome work, ! thank u for putting in so much effort and thanks to me also for making 1/5th effort to make it to the end of this video. good to see that u covered so many test cases, which made the explanation more clear.
This is one of the best explanations to the KMP algorithm, thank you :)
Finally understood this KMP in my 6years of studies. Theenks.💪🏼
Excellent attention to feedback
This is the first video from NeetCode that I can't seem to understand wow! speaks to the complexity of the algo or maybe I am just mediocre XD
Honestly, This was the best explanation I have found on the internet, and trust me I have watched a hell lot smfhhh
@NeetCode Please correct me if I'm wrong, but on 19:12, when you say "that's what the 1 tells us..", i think you meant to circle the 1st and the 2nd "A" in the text and not the 1st and 3rd "A".
It's amazing how stuff like this is actually free. Thanks dude!
Best KMP algo explanation ever. Thanks neetcode.
u make it so easy and understandable . ig this is the best video on kmp i came across.
That is super helpful. I finally understand this, two days
Thank you for this amazing video!
Finally, I understood this algorithm.
Best kmp explanation i've ever found on youtube!!!
this is the best video on youtube for this question
Appreciate Your hard work. It was hard. I will need to review again a few times to figure out and remember.
Thanks NeetCode, it's pretty hard to find a good explanation on the KMP algorithm and you did a great job of explaining it here. Would it be possible for you to cover the Aho Corasick algorithm at some point? I'm finding it difficult to find a good resource explaining that one and having a NeetCode explained version would be a nice follow up to this one as I believe Aho Corasick uses KMP to efficiently find substrings in strings along with Tries.
Great explanation! Thank you so much
Sir pls take questions from the previous week's contest. They were too odd and problem statement were not put up correctly. Thanks 😊
Yeah true, that's one of your longest videos but you explained KMP-algorithm very clearly
I do not understand the tricky part when building the LPS array, when i and j do not match, why move j by the VPS[i - 1]? Because move that way you will skip some middle elements. Is there a proof that garentee the longest prefix suffix?
yew, i also want answer for this logic
If prevLPS come backs to prevLPS=0 then it can further move max n-i steps ,that's why time complexity is O(N)
Simply beautiful explanation. Very near perfect one.
Tysm! I would have never understood this if I tried learning on my own.
Best explaination I found for KMP thanks
Very well explained thank you so much
first time in neetcode history* bro made it wild
prevlps is the value stored or the pointer to that location?
Very detailed explanation.Thank you very much
The problem with this explanation is while building the needle array,
when we have needle[i] == needle[prevLPS], we set the value,
lps[i] = prevLPS + 1 but you keep saying we are incrementing the value by 1 of prevLPS index value in lps array whereas we are setting the incremented value of prevLPS and not the index value of it i.e. lps[i] = prevLPS + 1 and NOT lps[i] = lps[prevLPS] + 1
Coincidentally the examples choosen had the same index value and the value inside lps array i.e. value at index 1 is 1 and value at index 2 is 2 that's why i think the choice of example was poor.
Other than that the explanation was great.
I am thinking same, and spent so much time on it tow find out explanation is wrong
Clean and precise, thanks @NeetCode
You always explain such this it is one of the best explanation🤩
best explanation on KMP on yt ❤
Thanks for this
hey Neetcode at timestamp 22:40, why was LPS[6]!= 6? because for the substring 'AAACAAA' -> prefix(AAACAA)==suffix('AAACAA') and that length is 6. please tell me if i am mistaken.
Hey guys, I have a question regarding the calculation of the LPS array. When it comes to the "else" condition, why do we let prevLPS = LPS[prevLPS-1] instead of decrementing prevLPS by 1? 🤔 THANKS.
I was wondering the same thing
If you found an explanation please share
@@prakhargupta4320 checj for other strings as well youy will get it
What a great explanation. Thanks!!!!!!
Great Explanation 🙌🙌🙌🙌
Thanks for the amazing explanation!
Enormous thanks for making this video!
24:10 I wonder why here we can say LPS[2]'s value means the first two chars match the 5th,6th chars. In my view when the LPS[2] is determined, we don't know the following matches, so its value can only tell the first two match the 1th,2th two (matching prefix-suffix numbers up to current bit). Since then LPS[2] haven't change, why has the meaning changed? Thank you the same.
I was asked this for FAANG interview
Thank you for the video.
Good stuff Sir ☺️
Best explanation! Thanks so much
Hats off to your effort. 👍🏻
Awesome explanation!
So totally helpful! Thanks!
Hi! I'm still relatively new to DSA so would appreciate if anyone can guide me with my question?
I am confused as to why we need to work with KMP algorithm when we can directly use the indexOf() method to check if pattern exists in the String.
I agree and understand that indexOf() itself might have some underlying algorithm that gets the work done for us.
Do we learn this for scenarios where we can't use pre-defined methods and need to write our own code?
Thanks Man!Saved mine time❤
Tbh if you wrap your head around the working of the KMP algo, it’s not that complicated and pretty astonishing what it achieves
Great explanation! 👍
Amazing video and explanation.
I was like after checking out what others solutions made by other users beats mine after I just spent my whole day learning this algorithm, and guess what? THIS:
class Solution:
def strStr(self,haystack: str,needle:str)->int:
if needle in haystack:
return haystack.index(needle)
else:
return-1
Probably because list.index implements this algorithm (or similar) but in C rather than Python.
Side note: Since list.index throws a ValueError if the substring isn't found, it's probably better to do this as a try-except block rather than checking if the substring exists then finding it.
That just went through my brain. thanks
I did this yesterday on leetcode. After solving it turnns out to be KMP algorithm.
If you think KMP is complicated, try Boyer-Moore using both shift-value table and good-suffix rule.
Thank you so much!
I dont understand why prevLPS = lps[prevLPS - 1]? is that always right?
cant we use rabin karp algorithm it also takes o(|n| +|m|) right?
Now I finally understood why all my Computer Science peers in uni always told me "Knuth's algos are pure SUFFERING" XD Thanks for this very nice explanation, man! Like :+1:
this was so helpful!! thank u!!
Great explanation.
Very helpful, thank you!
Not me legitimately saying "wow" when you went dual screen mode 😭
Great work. Keep it up :-)
I love the audacity of Leetcode to post this question as "EASY"
Loved this video!
this was really helpful thanks
Incredible explanation! Thanks for the video.
I don't understand why we use prevLps as an index , but set the value from lps[prevLps - 1]; Why value can be used as index?
you are awesome, thank you
thank you very much
am I correct that these algorithm does not work correct for such case
string haystack ("ababcaababcaabc");
string needle ("ababcaabc");
＠23:34 “C“ is at index three, not index four; 0, 1, 2, 3…
Thanks a lot.
Best explanation
KMP is great for falling asleep to
at 24:28 you said that that we would take lps[prevLPS] and add 1 to it but in the code in first condition you wrote lps[i]=prevLPS+1 and not lps[prevLPS] +1
bro i got google screening interview in few days - i remember u said in one of the videos that you can find the screening question online, but i dont see it. although i have prepared from leetcode. But i remember u said the question are easy, it not that easy also, its all good medium level problems