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.
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 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.
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.
For people wondering like me whether the LPS computation is the same as Z-function of a string... It's conceptually similar, but not the same, a simple explanation would be, that LPS matches the prefix of s with the suffix "ending" at position i, while Z-function matches the prefix of s with the substring starting "from" i.
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!!
@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".
The part of constructing lps can be simplified a little. This is from 214. Shortest Palindrome question. def prefix_table(self, s): lps = [0] * len(s) prevLPS = 0 for i in range(1, len(s)): while prevLPS > 0 and s[i] != s[prevLPS]: prevLPS = lps[prevLPS - 1] if s[i] == s[prevLPS]: prevLPS += 1 lps[i] = prevLPS return lps
Now is 1:21, I am a embedded dev and I don't even use this much algorithm but YT suggest me this bro and now I am here :)). God damn this is so hook, you nailed it so much better than my professor back in the day.
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.
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 found it so hard to understand the inner else block. But it clicked for me after 24:00 when you explained what the value 2 meant which was pointed to by p
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.
at 19:15, i thing it's wrong or miscommunication because prefix[1] = 1, means pat[0] = pat[1], it does not means pat[0] = pat[2], and it is being said there. Please someone clarify.
You're wrong, with ur explanation, the KMP approach remained easy. Literally I can visualise the pointer iteration in my mind. Kudos @NeetCode One more point I would like to add, While filling the LPS (Longest Prefix Suffix) array, we essentially filled the length of the valid substring (which matches with LFS criteria). But when we're gonna use it in the KMP algorithm part, we treat the array values as indexes, specifically the index in the needle where we'll start matching with the haystack index. How we know we can skip the indexes from 0 to index - 1? Because of this check haystack [i] == needle [j] and we increased both I and j. P.S : We calculated the LPS array independently, with no knowledge about the haystack string. Hope it helps!
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?
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 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?
Hi I have a question in the code when needle[i] == needle[preLps], you add lps[i] = preLps + 1, but in the vedio you said that you add the lps value. so why you add index in the code but it works?
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
![Noob To Max With DRAGON REWORK In Blox Fruits [FULL MOVIE]](http://i.ytimg.com/vi/LnBMOinoOvA/mqdefault.jpg)
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 !
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
Learn same algo from Abdul Bari video on youtube. You will understand it in first attempt
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
Yes but I was instead able to come up with Rabin-Karp algorithm instead lol. Well the initial intuition actually.
I saw many explanations on kmp algo, but the explanation you provided is the best and the easiest to understand, kudos to you !
If someone says they can explain KMP better, they are lying. It doesn't get any better than what you just did. Amazing Neetcode. 🙏
lmao.. this guy says this algo is complex.. just watch abdul bari's video on KMP. He has explained it in a much better and easier way
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!
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
At 22:00 I think I really started getting it!
Thanks Neetcode for the clear explanations as usual.
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
Beautiful explanation, only the one who understands the logic can explain others with such clarity
why do u sound like you're explaining it to me for the fifth time
I don't usually watch RUclips videos for LC, but KMP had my brain on buffer. Your example walkthrough just made it click for me. Very Neet solution.
KMP is great for falling asleep to
Thank you for your hard work ! Video is incredibly useful and easy to understand.
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 KMP solution I've been seen, very clear, thank you!
Thanks Mr.Neet for listening.
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
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.
You saying again and again it's tough and really it's. But you make the algorithm very easy by your explanation. Superb work....
Wow. You listened to the feedback from viewers. Goddamn legend ✌
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.
For people wondering like me whether the LPS computation is the same as Z-function of a string...
It's conceptually similar, but not the same, a simple explanation would be, that LPS matches the prefix of s with the suffix "ending" at position i, while Z-function matches the prefix of s with the substring starting "from" i.
One of the best explanation out there for this hard hard hard algorithm
Excellent attention to feedback
prevlps is the value stored or the pointer to that location?
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!!
Thanks a ton man! I've watched a lot of videos on kmp but I found your explanation super easy.
Finally understood this KMP in my 6years of studies. Theenks.💪🏼
@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".
Yeah
The explanation of lps array is bit confusing in the above video,
better explanation can be found here -> ruclips.net/video/ziteu2FpYsA/видео.html
Great explanation. Finally understood LPS.
Thank you so much for your efforts. I have understood the logic behind KMP intuitively🤟
The best explanation yet, thank you. I stumbled across some Indian guys and they explained to me that they know how it works 😢
Honestly, This was the best explanation I have found on the internet, and trust me I have watched a hell lot smfhhh
This is one of the best explanations to the KMP algorithm, thank you :)
Thanks
u make it so easy and understandable . ig this is the best video on kmp i came across.
Best KMP algo explanation ever. Thanks neetcode.
this is the best video on youtube for this question
The part of constructing lps can be simplified a little. This is from 214. Shortest Palindrome question.
def prefix_table(self, s):
lps = [0] * len(s)
prevLPS = 0
for i in range(1, len(s)):
while prevLPS > 0 and s[i] != s[prevLPS]:
prevLPS = lps[prevLPS - 1]
if s[i] == s[prevLPS]:
prevLPS += 1
lps[i] = prevLPS
return lps
That is super helpful. I finally understand this, two days
Now is 1:21, I am a embedded dev and I don't even use this much algorithm but YT suggest me this bro and now I am here :)). God damn this is so hook, you nailed it so much better than my professor back in the day.
Best kmp explanation i've ever found on youtube!!!
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
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.
Thank you for this amazing video!
Finally, I understood this algorithm.
It's amazing how stuff like this is actually free. Thanks dude!
I‘ve watched this onve before i started studing out of curiosity and now watch it again because i need it
I found it so hard to understand the inner else block. But it clicked for me after 24:00 when you explained what the value 2 meant which was pointed to by p
best explanation on KMP on yt ❤
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.
＠23:34 “C“ is at index three, not index four; 0, 1, 2, 3…
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.
Great Explanation 🙌🙌🙌🙌
Thank you for your excellent explanation ❤
at 19:15, i thing it's wrong or miscommunication because prefix[1] = 1, means pat[0] = pat[1], it does not means pat[0] = pat[2], and it is being said there. Please someone clarify.
You're wrong, with ur explanation, the KMP approach remained easy. Literally I can visualise the pointer iteration in my mind. Kudos @NeetCode
One more point I would like to add,
While filling the LPS (Longest Prefix Suffix) array, we essentially filled the length of the valid substring (which matches with LFS criteria).
But when we're gonna use it in the KMP algorithm part, we treat the array values as indexes, specifically the index in the needle where we'll start matching with the haystack index.
How we know we can skip the indexes from 0 to index - 1?
Because of this check haystack [i] == needle [j] and we increased both I and j.
P.S : We calculated the LPS array independently, with no knowledge about the haystack string.
Hope it helps!
Clean and precise, thanks @NeetCode
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.
the simplest explanation ❤🔥❤🔥
Appreciate Your hard work. It was hard. I will need to review again a few times to figure out and remember.
Sir pls take questions from the previous week's contest. They were too odd and problem statement were not put up correctly. Thanks 😊
Best explaination I found for KMP thanks
Yeah true, that's one of your longest videos but you explained KMP-algorithm very clearly
Time complexity explained (intuition) : 24:50
Tysm! I would have never understood this if I tried learning on my own.
At 23:44 there is a small error: you say that prevLPS is 4, but actually is 3, because the array starts from 0
Hats off to your effort. 👍🏻
Good stuff Sir ☺️
Very well explained thank you so much
You always explain such this it is one of the best explanation🤩
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?
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
first time in neetcode history* bro made it wild
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
cant we use rabin karp algorithm it also takes o(|n| +|m|) right?
Very detailed explanation.Thank you very much
Thanks Man!Saved mine time❤
Great explanation! Thank you so much
after watching for 35 mins, i decided to just memorise it :D call me a god
Great explanation! 👍
Hi I have a question in the code when needle[i] == needle[preLps], you add lps[i] = preLps + 1, but in the vedio you said that you add the lps value. so why you add index in the code but it works?
Enormous thanks for making this video!
What a great explanation. Thanks!!!!!!
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
I was asked this for FAANG interview
Thanks for the amazing explanation!
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?
am I correct that these algorithm does not work correct for such case
string haystack ("ababcaababcaabc");
string needle ("ababcaabc");
Thanks for this
Best explanation! Thanks so much
I did this yesterday on leetcode. After solving it turnns out to be KMP algorithm.
So totally helpful! Thanks!
I dont understand why prevLPS = lps[prevLPS - 1]? is that always right?
Good explanation !
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
this was so helpful!! thank u!!