+ashish paralkar Thanks a lot for your kind feedback and you are right in that it took some patience to create this video. Ashish, we would really appreciate if you can spread the word about IDeserve(www.ideserve.co.in) in your peer circles. Cheers, Team IDeserve
@@mohammadanasmudassir9443 you need test cases, very thorough ones. I was also stuck at that point where you are - I think. that 1 famous Stack overflow post has a full chain of comments all of which taken together paint the full picture.
Quite brilliant. I went through 3-4 videos and 4-5 wiki/tutorials before this and I was extremely frustrated. Finally my friend recommended your video and it is easily the best. Thanks a ton for putting in the effort to make this video. Took me two passes to fully understand the code walkthrough but you've done a great job.
I was struggling the whole day to understand this topic and now finally I saw this video. I feel relieved now , very well explained along with the code.
Thanks a lot for your words Shefali :) We are striving hard to make understanding algorithms easier. We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like Algorithm Visualization, Learn Together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.
This is best lecture, I have found on UA-cam to understand the Manacher's Algorithm. The way you teach It reflect how much deep understanding You have. Thank You for this wonderful explanation, It saves lot of time and effort.
After spending 1.5 days on this problem, and reading that 4 pg GFG article, thank God I found the link of this video in the discuss section of GFG. This is the Best Explanation till now of Manacher's Algo. Thank You @IDeserve for this wonderful explanation :)
couldn't get anything from the explanation alone, but as soon as you started showing the code, everything you explained started to click into place, very much well done
Was really struggling to the point I was gonna skip this algorithm. You helped me understand it, thank you so much for your help! This is way better than some videos with more views.
I was struggling yesterday night switching from video to video, at first, I didn't understand your explanation, but now it's clear. Thank you very much.
Thanks for your kind words :) We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like Algorithm Visualization, Learn Together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.
Your explanation is Amazzing, simple and easy to understand, probably the best for such a complex algorithm. please keep it up. Thanks for this video and thanks to Mr Manacher as well for this algorithm.
+Wenhao Du Thanks a lot for your words! It is very encouraging to hear such comments! Also please check out our website at: www.ideserve.co.in It has features like algorithm visualizations, learn together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.
Excellent explanation for a complex algorithm. Minor correction of logic: If condition after 'while' loop is going to run every 'i' values that are greater than R. Example: 'ABABABACDEFG' try this as an example and check C and R values would change for i > 15 and overwrite C and R values to lower values. This will result in a wrong output. So, this 'if' condition should check for P[i] should be greater than P[R] to change C and R to new values. Replace if(i + P[i] > R) with if(P[i] > P[R]) Thank you for the great explanation.
Superb explanation. I was able to follow through without any trouble. Hats off. Would be great if you could explain KMP algo and Z algo as well. Thanks for this one.
Really great explanation. Watched couple of videos for this algo and yours is the best one. Very precise and your code walkthrough was awesome which made it complete. Appreciate your efforts in making those slides. Your videos would be mine first goto from now. Happy to share!
+Owen Xu Thanks a lot for your words! We are striving hard to make understanding algorithms easier. We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like algorithm visualizations, learn together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.
This is an excellent video. Just one suggestion for future videos: in the example that you went over, we never had the case where we had to take R-i over P[mirr]. It would be good for the example to include this case.
Awesome! This is the most intuitive explanation, even people dull like me can understand the point of this algorithm now! Nice job, looking forward more of your publish!
+吴佩 It's really encouraging to hear comments like these. Yes we are uploading new videos on regular basis. So, stay tuned :-). Please feel free to let us know if you would like us to upload a video for a particular topic/algorithm. We will really appreciate if you can spread the word about IDeserve(www.ideserve.co.in) in your peer circles. Thank you, Team IDeserve
It's actually quite a simple algorithm once we become familiar with the concept. Basically, copying over the mirrors expansion length if the index lies within the current right boundary means we don't calculate the expand length from scratch at every index - we use the symmetric property of palindromes to give us a O(n) time.
Great Explanation, no other video on YT does the explanation this way, I was looking for video like this. Eg: "what is making the brute force algorithm to run in O(n^2) and how it can be optimized"
Spent whole day to understand this from other resources result ==> ~NULL Spent time here understood in 2 go !! Recommended!! Thank you for the best explanation.
+Andrea De Domenico Thanks a lot for appreciating! There are many more videos coming soon. Also, you can let us know any interview topic or question of your choice that you would like to see on IDeserve. Thanks, -Team IDeserve.
thank you so much, sir, you are great ...... I found a lot of videos on manchester's algo but all that was waste material. you are a gem in terms of algorithms.
Actually I was going to leave this algorithm after seeing Tushar Roy's video knowing how complex this is but after seeing yours the rest is history. Just make stuff like this and make UA-cam a better place to learn✌️
You can make it even faster if you'll check for "larger" palindrom, so when we've found the size 7 for example, at the start we check chars at that boundary. And I really can't get why it's only 2 "passes" through the string, because if it's string of same char, it will check the same char multiple times, like n/2 times for the first and n - i / 2 for the rest.
2:25 - How is this O(n)? At each alphabet, we are again going both the sides to see if it is a palindrome. For worst cases like AAAAAAAAAA, won't it be O(n2) ?
Good question! Below is my explanation. The time complexity is determined by the number of times you compare the chars. The result of each comparison is either "equal" or "not equal". Whenever the result is "equal", the right boundary moves, which cannot happen more than O(n) times. When the result is "not equal", the char is done and you move on to the next char, which cannot happen more than O(n) times either. So the algorithm is guaranteed to take O(n) time in any case.
+Jacob Hubbard Thanks a lot for your words! It is very encouraging to hear such comments! We are striving hard to make understanding algorithms easier. Please check out our website at: www.ideserve.co.in. It has features like algorithm visualizations, learning together and many more coming soon!
If we store a max, in this case 7, why can't we exit early when the center of the palindrome at i cannot possibly be greater than 7? A palindrome at i of length 7 or more would hit end of string. Am I wrong or it perhaps not worth checking for this case?
Thanks forceinfinity for your kind words :) We are striving hard to make understanding algorithms easier. We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like Algorithm Visualization, Learn Together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.
8 years old but still better explanation compared to newer videos explaining the same
Thank you :)
GFG took 4 articles to explain this. This man nailed it in only 15 mins .
Thanks Ritik!
This is really true.... :)
23 min lie h bhai acche se dekh
epic explanation man. watching it twice did it for me. i can imagine the patience it took you to make these 176 slides
+ashish paralkar Thanks a lot for your kind feedback and you are right in that it took some patience to create this video. Ashish, we would really appreciate if you can spread the word about IDeserve(www.ideserve.co.in) in your peer circles.
Cheers,
Team IDeserve
@@IDeserve Thanks for making these slides and video! How long did it take you to make these slides?
Bro mai ni samajh paya
Save time: I watched all of Manacher`s algorithms on youtube, this is the best one.
Thanks Ece!
I have honestly never encountered an O(n) algorithm that is tricker than this. You give the best explanation though, thank you.
Thank you so much for your kind words Jon!
Ukkonen's suffix tree construction would do if you want to see that. 😄
@@Adityarm.08 That algorithm is an atrocity. I was only able to code 80% of it and cannot understand the online solutions :/
@@mohammadanasmudassir9443 you need test cases, very thorough ones. I was also stuck at that point where you are - I think. that 1 famous Stack overflow post has a full chain of comments all of which taken together paint the full picture.
Ukkonen is a nightmare
Took me over a week to finally understand all of this. This is one of the hardest algorithms out there. Outstanding work!
Thanks 😊
thank you ! Great job !@@IDeserve
Dude. This was hands down the BEST explanation for the algorithm I've ever heard. Thank you so much!
Thanks Daniel!
Quite brilliant. I went through 3-4 videos and 4-5 wiki/tutorials before this and I was extremely frustrated.
Finally my friend recommended your video and it is easily the best. Thanks a ton for putting in the effort to make this video.
Took me two passes to fully understand the code walkthrough but you've done a great job.
Thank for your nice words Kayysean99!
Epic video on Manacher's algorithm . Very clear and precise explaination. Appreciate the effort you have put to create this content.
Thanks Zeeshan!
IDeserve, you definitely deserve a standing ovation! I can't wait to checkout your other videos. Thank you!
Thanks bro!
I was struggling the whole day to understand this topic and now finally I saw this video. I feel relieved now , very well explained along with the code.
Thanks a lot for your words Shefali :)
We are striving hard to make understanding algorithms easier.
We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues.
Also please check out our website at: www.ideserve.co.in
It has features like Algorithm Visualization, Learn Together and many more coming soon.
Please check it out and leave us a comment there!
Thanks,
-Team IDeserve.
Best explanation on Manacher's alg I've ever seen! Really appreciate you for sharing this!
Thanks Ziyan!
This was pretty difficult to understand but your efforts are commendable. Thank you
So far, the best video for understanding it, rather than just explaining the process
Thank you so much Doug for your kind words :)
This is best lecture, I have found on UA-cam to understand the Manacher's Algorithm. The way you teach It reflect how much deep understanding You have. Thank You for this wonderful explanation, It saves lot of time and effort.
Thank You! 😊
I agree with you. When I started thinking about revising this algorithm, I came here.
great explanation, finally understood the enigma of Manacher's algorithm. keep doing the cool work
Thanks Imran!
I don't think this could've been explained any better than this. Appreciate your efforts, sir.
Keep up the good work.
Thanks
Thanks Shubham!
After spending 1.5 days on this problem, and reading that 4 pg GFG article, thank God I found the link of this video in the discuss section of GFG. This is the Best Explanation till now of Manacher's Algo. Thank You @IDeserve for this wonderful explanation :)
Thanks Abhrajyoti!
wow man the amount of effort you took to explain in this video is incredible, take a bow sir
Thanks Arnab ☺️
couldn't get anything from the explanation alone, but as soon as you started showing the code, everything you explained started to click into place, very much well done
I've watched around 5 videos and read 6 articles on this topic, and this video is the best and lucid explanation of the topic. Thankyou!
Thanks Tushar! 😊
I didn't think I fully got it when I finished the video, but then I tried to code it without referencing back here and it worked. Thanks!
Nice explanation... I watch the video a couple of times, but I understood it perfectly. Thanks man for sharing this.
Thanks Kshitij for kind words!
Thanks, the best walk-through of the algorithm I've seen so far!!
Why'd you guys stop making videos?
gone through many videos of manacher's algorithm.But this is the one where my searching stopped.Thank you for this awesome content
Thanks Priyanshu!
best explanation found till now !!
Was really struggling to the point I was gonna skip this algorithm. You helped me understand it, thank you so much for your help! This is way better than some videos with more views.
Thanks for the comment Shivansh :)
I was struggling yesterday night switching from video to video, at first, I didn't understand your explanation, but now it's clear. Thank you very much.
Thanks for your kind words :)
We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues.
Also please check out our website at: www.ideserve.co.in
It has features like Algorithm Visualization, Learn Together and many more coming soon.
Please check it out and leave us a comment there!
Thanks,
-Team IDeserve.
I don’t give up often but when I do it’s Manacher’s algorithm 😂
🙈
+1 😒
Seriously, the best explaination I could get on whole youtube.
Thanks :)
Thanks Prabhav!
Your explanation is Amazzing, simple and easy to understand, probably the best for such a complex algorithm. please keep it up. Thanks for this video and thanks to Mr Manacher as well for this algorithm.
Thanks Sudipta!
been trying to understand it for hours and I understood it perfectly in a 15 minute video. thank you so much!
Thanks :)
Thanks man. I struggle for whole day to understand it, but you made it so easy. Really appreciate your effort.
Thanks Ankish!
Excellent and very detailed presentation of a very complex topic. A lot of work must have gone into the graphics.
Thanks Kunal!
The "thinking pause" did it for me. I am floored
I've seen many top youtuber's tried to explain but only you succeeded.
Best Manacher's Algorithm explanation I have ever seen.
Thanks!
Hey, I love these videos. These are definitely helping me as I prepare for the interview for my internships.
+Wenhao Du
Thanks a lot for your words! It is very encouraging to hear such comments!
Also please check out our website at: www.ideserve.co.in
It has features like algorithm visualizations, learn together and many more coming soon.
Please check it out and leave us a comment there!
Thanks,
-Team IDeserve.
You are so good that you could have come up with this algorithm on your own. Thanks!
Thanks Nisheet for your kind words!
I watch it again after almost 2 years, I have to say this video is by far the BEST algorithm on youtube ever!!!
Hey James, welcome back!
the best and most clear explanation of manacher on YT
Thank you :)
went through a lot of videos to understand this algorithm. But this one is the best so far.
Excellent explanation for a complex algorithm. Minor correction of logic:
If condition after 'while' loop is going to run every 'i' values that are greater than R.
Example: 'ABABABACDEFG' try this as an example and check C and R values would change for i > 15 and overwrite C and R values to lower values. This will result in a wrong output.
So, this 'if' condition should check for P[i] should be greater than P[R] to change C and R to new values.
Replace
if(i + P[i] > R)
with
if(P[i] > P[R])
Thank you for the great explanation.
A really good explanation. Thanks for your hardwork man.
Thanks Aatish!
@@IDeserve Is the video on explaining the time complexity of this algorithm uploaded ?
What an explanation sir. Keep it up. The best thing was you dry ran the code also with values, i didn't require even a pen and a copy to understand.
Thank you so much for your kind words Sitesh!
I have watched other videos also. But your one made me understand it completely. Kudos to you buddy. Keep going.
Thanks Ashwani!
Superb explanation. I was able to follow through without any trouble. Hats off. Would be great if you could explain KMP algo and Z algo as well. Thanks for this one.
Thanks Shubham!
Extra ordinary explanation of the mental modal behind Manacher's algorithm. The best of the best.
Thanks Akila!
Such a easy explanation, thank you sir
Thanks Prateek!
Bro you saved my day with your wonderful explanation, definitely subscribing!
I had decided to skip manachers algo for upcoming placement! Now I have it in my toolkit! thanks man
gr8 job!
All the best for the placements!
Really great explanation. Watched couple of videos for this algo and yours is the best one. Very precise and your code walkthrough was awesome which made it complete. Appreciate your efforts in making those slides.
Your videos would be mine first goto from now.
Happy to share!
Thank you so much for your kind words Harmeet!
Thank you sir! It's a really helpful video!
Thanks Miguel! 😊
Great video. I have read some blogs about this Algorithm and still not understand.
Withi your explaination, it become clear to me! Thanks very much!
+Owen Xu
Thanks a lot for your words! We are striving hard to make understanding algorithms easier.
We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues.
Also please check out our website at: www.ideserve.co.in
It has features like algorithm visualizations, learn together and many more coming soon.
Please check it out and leave us a comment there!
Thanks,
-Team IDeserve.
Awesome explanation, loved your work and effort. You actually deserve it!!
Thanks Savan!
very clear explanation. Great work. Thank you!
Thanks Puneet!
Awesome explanation. Thank you very much. Appreciate your efforts.
Thanks Prashant!
the best explanation of manacher's algorithm, great buddy it really hepled me alot
Thanks Mihir!
This is an excellent video. Just one suggestion for future videos: in the example that you went over, we never had the case where we had to take R-i over P[mirr]. It would be good for the example to include this case.
Thank you a lot for your explanation! It is the video that is worthy to spend 24 minutes on it!
Thank you so much for your kind words Daniel!
Awesome!
This is the most intuitive explanation, even people dull like me can understand the point of this algorithm now!
Nice job, looking forward more of your publish!
+吴佩 It's really encouraging to hear comments like these. Yes we are uploading new videos on regular basis. So, stay tuned :-).
Please feel free to let us know if you would like us to upload a video for a particular topic/algorithm. We will really appreciate if you can spread the word about IDeserve(www.ideserve.co.in) in your peer circles.
Thank you,
Team IDeserve
I have been trying to understand this algorithm, but failing .. thanks ..just a single watch here on ur channel, I have understood it completely
Thanks for the extremely clear explanation! Tracing the code made it even better :)
You are welcome Tyler!
I looked at some other explanations and yours is by far the best. Thank you so much!
Thank you so much for your kind words Dario!
This was so helpful thank you! I appreciate all of the patience it took you to iterate through this.
Thank you so much for your kind words Glory!
Wonderful explanation, concise and apt :)
Helped me understand it till the depth. Great work, kudos !
Thanks Shaival for your kind words :)
Great explanation. I feel if there were indices on P[ ] then it would be easier to follow when you went through the code.
after rewinding and pausing crying finally it just clicked dont give up on this it is staple for palindromic problems
It's actually quite a simple algorithm once we become familiar with the concept. Basically, copying over the mirrors expansion length if the index lies within the current right boundary means we don't calculate the expand length from scratch at every index - we use the symmetric property of palindromes to give us a O(n) time.
23:48 minutes used for the best man !! Thank you so much for this finally got this😂
You are welcome!
This is awesome explanation , the visualisation helps a lot with understanding the idea behind the algorithm! Great job guys.
Thanks Li!
excellent explanation bro. your patience must be paid off. keep up good work...
Thanks Adarsh!
Great Explanation. Probably the best i have come across so far.
Great Explanation, no other video on YT does the explanation this way, I was looking for video like this. Eg: "what is making the brute force algorithm to run in O(n^2) and how it can be optimized"
Thanks Teja!
Spent whole day to understand this from other resources result ==> ~NULL
Spent time here understood in 2 go !!
Recommended!!
Thank you for the best explanation.
Thanks Ayush for your kind words!
+Andrea De Domenico
Thanks a lot for appreciating! There are many more videos coming soon. Also, you can let us know any interview topic or question of your choice that you would like to see on IDeserve.
Thanks,
-Team IDeserve.
I would recommend most of the difficult and medium level questions from leetcode and their principles.
Sir you nailed it . Thank you so much for awesome explanation 🙂
Thank you for your kind words! 😊
you have done a good job debugging the code. keep it up bro.
Thank you so much Sayed for your kind words :)
thank you so much, sir, you are great ......
I found a lot of videos on manchester's algo but all that was waste material.
you are a gem in terms of algorithms.
Thanks Ashutosh!
Nice explanation sir, other youtubers video are little difficult to understand on this topic.
thanks man. explanation is so good!!
Thanks Glenn!
If 'i' lies within boundaries we can directly copy mirror length to 'P[i]' but in the code why do we write 'min(R-i, P[mirr])' ?
Very good explanation Thanks you very much!
Thanks Rejeti!
Best explanation On the INTERNET.
Thanks Saurabh!
Awesome work man. Best explanation ever i have found on online.
Thank you so much for your kind words Tanmoy 😀
These repetitive comments on how brilliant this video was tells us about this video...from my side I really appreciate your efforts :)
Thanks Anirudh!
Thanks man!! You are a good teacher. I got the central idea after watching your video once. Now, I can try coding it on my own.
Thank you so much for your kind words Prudvinath!
youtube recommended this, glad it did
Thanks!
you definitely deserve a subscription man.
Thank you so much for your kind words Ram!
Actually I was going to leave this algorithm after seeing Tushar Roy's video knowing how complex this is but after seeing yours the rest is history. Just make stuff like this and make UA-cam a better place to learn✌️
Thank you so much Ram!
How come the complexity is O(n) if there is a while loop inside for loop, worst case should be O(n^2)
Agreed, it is stated the correct time complexity on the slides. The title of the video has wrong complexity.
You can make it even faster if you'll check for "larger" palindrom, so when we've found the size 7 for example, at the start we check chars at that boundary.
And I really can't get why it's only 2 "passes" through the string, because if it's string of same char, it will check the same char multiple times, like n/2 times for the first and n - i / 2 for the rest.
2:25 - How is this O(n)? At each alphabet, we are again going both the sides to see if it is a palindrome.
For worst cases like AAAAAAAAAA, won't it be O(n2) ?
Good question! Below is my explanation.
The time complexity is determined by the number of times you compare the chars. The result of each comparison is either "equal" or "not equal". Whenever the result is "equal", the right boundary moves, which cannot happen more than O(n) times. When the result is "not equal", the char is done and you move on to the next char, which cannot happen more than O(n) times either. So the algorithm is guaranteed to take O(n) time in any case.
Superb explanation...!!!! finally understood algo..!!!
Thanks you for your kind words Sachin!
Good explanation man...Try to explain all the important algorithms like this...
Great work. Best explanation I've seen yet.
+Jacob Hubbard Thanks a lot for your words! It is very encouraging to hear such comments! We are striving hard to make understanding algorithms easier.
Please check out our website at: www.ideserve.co.in. It has features like algorithm visualizations, learning together and many more coming soon!
which animation software are you using?
best video to understand Manacher's Algorithm.👍👍
Thank you!!
If we store a max, in this case 7, why can't we exit early when the center of the palindrome at i cannot possibly be greater than 7? A palindrome at i of length 7 or more would hit end of string. Am I wrong or it perhaps not worth checking for this case?
Excellent presentation. Hugely helpful in understanding the algorithm
Thanks forceinfinity for your kind words :)
We are striving hard to make understanding algorithms easier.
We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues.
Also please check out our website at: www.ideserve.co.in
It has features like Algorithm Visualization, Learn Together and many more coming soon.
Please check it out and leave us a comment there!
Thanks,
-Team IDeserve.
Directly accessing T[i+1+P[i]] and T[i-P[i]-1] without checking if they are breaching string boundaries(i+1+P[i] >= T.length() and i-P[i]-1