Manacher's Algorithm | Longest Palindromic Substring

[@suhanibajpai4025]

this is the best video among all the videos on youtube explaining manacher's algorithm

[@ShariqueAkhtar]

One of the best explanations on the internet on Manachers Algo

[@dhruvsingh5190]

best explanation found till now for this algorithm.🔥🔥

[@Lime-rr6te]

this was the best manachers algo explanation i found, better that tushar roy, tech dose, nick white and so many others

[@zzzzzzzmr9759]

very clear and comprehensive video. The best explanation for Manacher's Algorithm!

[@電腦騙徒剋星]

one of the youtuber that can explain manacher pretty well , respect

[@mokshajain7019]

Well Explained! Among all the videos about Manacher's Algorithm, your explanation is best. Thank you for making this video.

[@vivekpandya2163]

Just watching first 4 mins and I found its very fluent and easy to understand. 🙏

[@sanskarmani9094]

Too good. Thanks for explaining it in so simple terms and also for covering every case.

[@habilismayilov838]

greatest explanation of this algorithm on the internet.

[@ujjvalcodes3629]

Best explaination on the internet

[@user-coder-r6j]

Thank you a lot. Only this video deeply explained an algorithm!

[@shubhamagrawal7557]

Great Video. Thanks for the simple and intuitive explanation!

[@TobiasTEEHEE]

Great explanation, thank you!

[@gauravswain6907]

can not understand the psudo code in over 2 times watching this, I am ok with O(n)2.

[@shashwattripathi759]

All of your videos are just amazing ! Please make more videos...! Thanks a lot !

[@yaswanthchunduru5298]

Bro your videos are literally awesome.

[@vishalbhatane1608]

Nice explanation!

[@sylviazhang6786]

Thank you. It is very well explained.

[@gerardolastra4099]

Case 2 shown during 13:13 is wrong. p[i] >= p[i'] could be false, the palindrome centered in s_i' could extend back far beyond s_l. The conclusion that p[i] must be greater or equal to r-i is right, however.

[@siddharthabhi8704]

Yes, Case 2 is wrong, zxaxz#zxaxp , where i = index of 2nd a

[@motivation9718]

Great explanation brother.....

[@arghyadeepmandal4458]

Really good video 🙂🙂🙂

[@ArpitMarkana]

good explaination

[@xiaoxiaodeng3957]

Thank you, your video helps a lot.

[@satymshrma]

rather than adding hashes, you can just compare i,i (i being the centre). and make a function for it and fn(i,i) for odd, fn(i,i+1) for even.

[@zaksification]

Really great explainaion

[@yangthomas5721]

There is a little bug in the code, the --k step after expansion is mandatory.

[@laraibanwar1618]

Brother why did u leave making videos. They are all exceptional..

[@laraibanwar1618]

I will even subscribe ur channel.now Plz keep on uoloading

[@sanskarmani9094]

Can you also consider making a video on Ford Fulkerson max flow algorithm??

[@fluentalgorithms4847]

Sure!

[@pranavbansal9934]

best explanatiion!!

[@yangthomas5721]

Nice video

[@RAJPATEL-nm9nz]

Only one doubt why you have written, If(s[i-k]!=s[i+k]) --k

[@sarathchandrakalahasti1484]

Good explanation

[@GaonkaEngineer123]

//c++ code class Solution { public: string getModifiedString(string s, int n){ string sb=""; for(int i = 0; i < n; i++){ sb.append("#"); sb+=s[i]; } sb.append("#"); return sb; } public: string longestPalindrome(string s1) { int m=s1.size(); string s=getModifiedString(s1,m);// expand the string for even expansion of string cout

[@liupeng7757]

great!

[@Rohitkumar-ks9io]

Please provide a problem link related to this algorithm . you can provide it in description for further videos.

[@fluentalgorithms4847]

Ive added practice problems in the description.

[@GaonkaEngineer123]

Best !!!!!!

[@sahilsharma2952]

Can you make a video on sweep line algo as a whole?

[@fluentalgorithms4847]

I'll consider it. For now you can refer www.topcoder.com/community/competitive-programming/tutorials/line-sweep-algorithms/

[@lokeshkoliparthi9268]

I want to ask one thing that does this code only work for showing odd length substrings or will it work for showing even length palindromic substrings also. I tried for the string "bbbb" on this code and this code is not working. After seeing many videos, I finally understood Manacher's algorithm seeing this video. Thanks a lot and hoping to see more videos from this channel like this. Edit: One more thing I would like ask is this condition if(S[i-k]!=s[i+k]) required as I am facing problem with that line of code and finally removed and your code is running perfect for finding odd palindromes only. Once again Thanks for amazing explanation of concept.

[@kampatiraviteja7398]

thats great man

[@電腦騙徒剋星]

you need to add # yourself

[@aishwaryarastogi7265]

I think the algorithm will fail for a test case such as "cbbd"....

[@jakubjastrzebski9890]

So let’s see what happens here We rewrite your test case into # c # b # b # d # And then we simulate the algorithm… I will do it manually… i = 0 l = 0, r = -1 i is bigger than r, k = 0 We expand k to 1 and cannot further due to the left bound limitation, k = 0 again, p[0] = 0 We extend l to 0 and r to 0 i = 1 i is bigger than r again so k = 0 We push k to 2 and it fails due to mismatch k is 1 then p[1] = 1 We extend l to 0 and r to 2 i = 2 i is equal to r so we pass to else j is equal to 0, thus k starts at 0 We run the while loop and it fails at k = 1 due to mismatch then k = 0 p[2] = 0, l = 2 and r = 2 i = 3 i is bigger than r, so k = 0 After while it fails at k = 2 so k is 1, so p[3] = 1 and l = 2, r = 4 i = 4 i isn’t bigger than r j = 2, so p[j] = 0, thus k becomes 0, it fails for k = 3 so k = 2, p[4] = 2, l = 2, r = 6 i = 5 i isn’t bigger than r j = 3, p[j] = 1, k = min(1, 6-5) we start at k = 1, it fails at 2 so k stays at 1 p[5] = 1 l = 4, r = 6 i = 6 i isn’t bigger than r j = 4, p[j] = 2, so k is min(2, 0) k fails for 1 due to mismatch and k = 0, so p[6] = 0, l = 6, r = 6 i = 7 i is bigger than r so k = 0 it fails at k = 1 cause further it cannot extend, p[7] = 1, l = 6, r = 8 i = 8 i isn’t bigger than r so j = 6, k = min(0, 0) and then fails due to the range, so p[8] = 0, l = 8, r = 8, the end of algorithm, let’s see what’s the outcome… # c # b # b # d # 0 1 0 1 2 1 0 1 0 Seems correct to me

[@jakubjastrzebski9890]

@aishwaryastogi7265

[@vinaykirpalani5804]

brilliant explanation sir ! , thanks a lot

[@raj1307]

Can u make a solution video for the PALIN3 problem .. I am unable to understand the precomputation required in it... thanks

[@fluentalgorithms4847]

You can checkout my explanation here : discuss.codechef.com/t/palin3-editorial/4906/6?u=vedhant

[@raj1307]

@@fluentalgorithms4847 " To find ans[i], ans[i] = cnt[i+k][s[i]%3] - cnt[i][s[i]%3] will not work because sum[i] would have contributed to the sum right of I " Can u pls explain this line once? thanks

[@fluentalgorithms4847]

I have updated my explanation here : discuss.codechef.com/t/palin3-editorial/4906/6?u=vedhant

[@raj1307]

@@fluentalgorithms4847 Thanks a lot ... finally understood :)

[@tekbssync5727]

bhai pseodo code link wagera de diya karo

[@ankurrohilla4655]

❤❤❤

[@arshdeepkumar2586]

Great video, but try to make video at max 10 minutes it will help to retain viewers, because everyone is searching for solution in short time.