Longest Palindromic Substring Manacher's Algorithm

[@BRBallin1]

Normally your videos are very clear but this wasn't one of them.

[@NohandleReqd]

The algorithm was a bit complex, he did his best, i am sure!

[@rejetimeghavardhan7805]

Yes

[@jamjam3448]

me too, lol

[@caizhengyu]

At first I thought this is not clear but as I went through videos by others I found this one the best.

[@dianapoplacenel4764]

Way better than all written tutorials for manachers!!! this was amazing

[@joh1121]

Thanks a lot! Your tutorial is the best of all. The four cases were so clear and concise. After many struggles with the other written tutorials, I was finally able to implement the method by looking at the cases provided by you!

[@Fun2loot]

At 14:20 i feel there should not be 5 followed then 9, 5 should be replaced by 9. Since at end we are finding palindrome around x not a.

[@adilkhatri7475]

subtitles: hello friends my name is too sharp 😂😂😂

[@corepunch]

My name is Not Sure

[@pranjalpimpale8465]

wow, it was so hard to explain yet you did. Thanks

[@andreasleonidou3620]

Best tutorial on this algorithm! Very well explained and with examples!! Thank you!

[@bewareofnikhil]

As always, concise, accurate, and easy to understand explanation of a rather tricky algorithm.

[@harris7963]

LOL cOnCiSe

[@akashkandpal1832]

And the Oscar goes to Tushar Roy XD

[@srajitsakhuja5410]

Thank you for the video. The explanation was quite lucid. One suggested correction though, at 14:20, I suppose you would want to put the value '9' against the 13th element i.e. 'x' and not against the 14th element i.e. 'a'. Thanks again!

[@JacekKarwowski]

Why is the runtime complexity O(n)? Could you elaborate more on that topic?

[@rasheeqzaman3436]

I think the confusion is mainly because of the ""expansion for every element". That's why it kinda looks like it's O(n²). I scratched my head the whole day and finally understood how it's O(n). If you try to manually run this code( medium.com/hackernoon/manachers-algorithm-explained-longest-palindromic-substring-22cb27a5e96f ) on paper with some examples, you will find out that once the palindrome is calculated up to 'r', no other element enters the "while loop" again. Because the 'mirror' has already calculated the palindrome for that element. It will enter the "while loop" again when either the element is after 'r' or when the element's mirror's palindrome exceeds 'r'. I know what I am saying might sound like gibberish but once you have tried to run this algorithm in a '7-8' length word example, you will see I am trying to say.

[@neko419]

Thanks! Super clear. I finally understand Manacher's algorithm.

[@varaprasadbanda4951]

The explanation was great. Appending '$' in between every character to make it an odd length string was an interesting idea to reduce the code.

[@fan11657]

The clearest explanation of Manacher's algorithm I've ever seen!!! Thanks a lot!!!

[@ShubhaRamani]

Tushar you have explained Manacher's better than anyone !

[@joseville]

Let S be the string and LP[i] be the longest palindrome centered at index i of S. LP[i] = L implies that all(S[i-j] == S[i+j] for j in range(L//2 + 1)). As an example, the fact that LP[3] = 7 implies S[0] = S[6] S[1] = S[5] S[2] = S[4] S[3] = S[3] This leads to a question at 5:05, LP[4] >= 1 (the longest palindrome centered around S[4] is greater than or equal 1), but it also can't be >1 right? Assume, LP[4] > 1. If LP[4] > 1, then LP[4] must be at least 3 implying that S[3] and S[5] must be equal. However, noting that S[1] = S[5] due to LP[3] = 7, then S[1] = S[3] = S[5], but this implies that PL[2] >= 3 which is a contradiction given we know that LP[2] = 1. Therefore, LP[4] must equal 1.

[@yangyang4558]

This video is very helpful for me, while still, I need make 2 points clear by myself. 1. Why array[7] can't be the new center in 8m18s 2. Why the time complex is O(n)

[@NAVEENKUMAR-hr7fb]

its really though ...but i belived in tushar and watched twice and now i get it ...thanks man

[@johnsnow2149]

you messed up in explanation where you started to explain how to choose next center may be around 3:00 . without explaining logic fully ..... you kept moving ... lost you there

[@jimmcgaw]

This is where I got lost too. The math clarified it when I worked it out. Since the "a" at index 4 will have the same possible palindrome length around it as the one at index 2, and since the max palindrome length of that character is 1, 4+1 does not take you outside the bounds of the longest palindrome we have since encountered, ie 5 < 6. But, the "b" at index 5 is like the "b" at index 1, in that it has a longest palindrome around it of length 3. Since 4 + 3 takes us outside the upper bound of the longest palindrome, whose upper bound index is 6. So, since 7 > 6, it's a candidate. This is what he means when he says "b" at index 5 might possibly expand outside the bounds of the longest palindrome we've encountered so far.

[@PIYUSH61004]

This video really helped me in understanding this algorithm... Keep up the good work!

[@vipinyadav-to1wc]

At 14:28, I think you want to put 9 corresponding to 'x' rather than 'a'. Thanks for the video. very well explained !

[@slowdown_]

since when is "abb" a palindromic substring?? what am i missing here? ... 0:21

[@jamesb8223]

He obviously meant to select 'bb'. Small error.

[@jumanakarwa5108]

Hi Tushar, at 13:33, we have found the palindrome of length 11 at position centering at position > (N/2) where N is the length of the string. Can we stop at a palindrome length > N/2 and at a centering position >= stringLength/2, since the next 2 chars would be contained in the current large palindrome. Or can we in short ensure in this example that we do not process after palindrome length 11 is found, or could there be a corner case there ?

[@SatyanarayanaBolenedi]

Good question! I guess u r correct. there is no point in proceeding further to N/2, if you are palindrome length is already >= N/2.

[@paramagurug9237]

Not really will be true for all cases - consider "c b a x a b a x a b a x a", the palindrome at b (position 6) will be 9. the Value 9 > N / 2 (N=14). But at position 8 with x as center, the palindrome value is 11 (if we break, we'll miss this condition). Even for best cases, if the characters included in the larger palindrome then we could simply substitute the mirror values, which is just assignment and can be in o(N).

[@bharatgulati8531]

@@paramagurug9237 the case above that you shared has the b(position 6) towards the left side (and not past the halfway point) as the total length of the string is 13 so jumana's suggestion still holds. We can restate the above condition in the following manner instead - when the (number of chars towards the right of the next possible center < half of the maximum palindrome string found till now) we can say that the current maxima will be the global maxima even after those chars are processed.

[@DeepakGupta-yv8ft]

your videos are amazing. keep up the good work.

[@yanivgardi9028]

Thanks Tushar, another great video. question though - on 14:27 you wrote "9" in index 14 instead of in index 13. am i missing something here ?

[@Fun2loot]

5 should be replaced with 9, since we are finding with respect to x. When we reached at point x we had >=5 situation, then again look with respect to x we get 9.

[@jeffabc1997]

Incredible explanation... WOW!!!!

[@hongchuanli6322]

I am unable to follow you starting from 8:10 where you said that x at position 7 can't be further expand because position 10 is different from position 0 thus cannot be a 'a'. But at this point we should look at position 4 and check "if position 10 == position 4" and it seems to me position 4 is 'a' by accident. if I change you string to "cbaxabaxaba", this analysis doesn't hold.

[@paramagurug9237]

Very good question, in your example "c b a x a b a x a b a" - With b (position 5) as center we get 9 as palindrome, and when moving to x (position 7), the mirror (position 3 which is also x) will be within the range of left edge (exactly at left edge index which is 1). This will fall under the 3rd category (3. Palindrome expands till right edge and the mirror palindrome is still in the range - please watch full video) and x will become new center and will be palindrome 9.

[@sanjeevrajora7335]

what if i placed y at index 5 in array at 8:36,current array will remain of same size but palindrome around x(index 7) will go beyond current array.It will contradict what u say ,can u explain plz?

[@shashanksahu2146]

Thank You Tushar Sir for great Explanation

[@savithamariswamy9300]

Explaination was very clear and i understood this in the first watch itself. Thanks Tushar.

[@jvarunkumar]

Can u give a better explanation as to why this algorithm runs in linear time? The algorithm goes several times back and forth on the tape... Run time complexity is not as straightforward as u mentioned.

[@malharjajoo7393]

+Emma Bostian - How can you say that ? For every palindrome centre , he seems to be checking to the left and right ( this could be a max of n-1 also... ). Can you say how it is O(7n) and not O(n^2).

[@keliao2160]

but this algorithm doesn't expand from the center at any index right? It skips a lot. And also for calc the new length at a specific index, it takes use of the old data instead of calc from scratch. There must be a strict math way to prove the time complexity, it is not easy to see.

[@shreyas6589]

@@EmmaBostian what if you run it n times? O(nn) = O(n) or O(n^2)

[@weiranhuang3939]

@@shreyas6589 The right edge will never exceed the length of the string. So the inner loop will only run at most n times.

[@ihopethiscommentisntabusiv4670]

Amazing explanation, very clear. People who are complaining about not understanding... I don't know, its not that complicated, just watch it again a few more times? Its really not that hard to grasp.

[@surajthapliyal9374]

finally understood this complex algo, but not completely its time complexity .

[@prasadchaudhari1001]

Hello Tushar, I wanted to point out a small issue, which I am not sure if it is my implementation issue or some bug related to your algorithm but this algorithms seems to exceed time limits when we give a string with only a's having a length of 10^5

[@houyun5416]

read some webpages but can't understand. your video really help

[@abhineelnandi9552]

Thanks a lot Tushar sir !!!

[@LoiTran2K2]

NICE I don't know why people dislike your video

[@shubhamsinha3368]

thanks Tushar saved my hours on hanging out the same explainatory stuff on the web

[@cameronswartzell5251]

I kind of wish he had put in the math for how we determine the four cases: as discussed we just "looked" at the expansions centered on the new possible Ith value and determined it visually expanded over the boundaries of the current max palindrome. Case 4 specifically is if there is a prefix of (curr_len-1)/2, then the new center is (curr_len/2)+(prefix_len/2) right?

[@joseville]

Thanks for the video! Just a heads up, at 14:32 you marked the wrong cell. Marked cell 14 with 9, but should have overwritten cell 13's 5 with 9.

[@YoyoMoneyRing]

nice explanation...especially the 4 cases for centre selection

[@na-gi1xb]

you explained it perfectly

[@abhilashsulibela1414]

A very tough concept explained better than most other people out there! A great effort. Thank you for this video.

[@yozaam]

at 4:47 when you say this isde should be a mirror of this side thats when the algorithm just clicked !!! thank you very much , reading on geeksforgeeks did allow me to understand it so easily

[@shyamtripathy5084]

Its a nice video. I just wanted to ask you, that for any String(Odd/Even) we need to append "$" (2*n+1) ??? Or anything better suggestion u have ?

[@akash-kumar737]

At 14:30 you are supposed to replace 5 with 9.

[@yianghu5517]

hello tushar, I have question about subarray sum II, the problem is Given an integer array, find a subarray where the sum of numbers is between two given interval. Your code should return the number of possible answer. for example: Given [1,2,3,4] and interval = [1,3], return 4, because The possible answers are: [0, 0][0, 1][1, 1][2, 2], O(n ^ 2) method is easy to implemented, but how to solve that in O(nlogn) time? My teacher said I can calculate the prefix sum array, then sort the that array, then I can get the answer, it is unreasonable.

[@rootred3644]

Thanx Tushar made my life easy bro...

[@rootred3644]

[@jaatharsh]

11:01 didn't understand exactly why at this point we pick a new centre, can somebody please explain the reasoning?

[@compilations6358]

question : You directly said, "center is expanding this much" ,how is expansion measured? (eg: a[3] = 7) 2. Shouldnt we stop moving mid if END_ARRAY - mid < max(CENTRAL_ARRAY) /2. Doesnt make sense to keep moving on the mid

[@6shobhit]

At 12:22 you are saying that x should not be the centre. Based on my understanding "should not be centre" means we should not spend time in calculating the longest palindrome But you wrote 5 in front of x. How we could write 5 without computing ? I would really appreciate your help

[@paramagurug9237]

As per video, this condition falls under 4th point, where the mirror palindrome goes beyond the current left edge. So, at this point we have to take the minimum of (mirror value and 2* (Right edge index - current index) + 1). In this case the value will be 5 - Min (7, 2* (9 - 7) + 1). If you look into the code : line no. 98 handles this (where "end" is right edge index, j = current index and i is the center). T[j] = Math.min(T[i - (j - i)], 2 * (end - j) + 1);

[@sunilnk95]

can you explain this part clearly?

[@rushabhmukkirwar3600]

this was clearly the only video till now that totally messed up!!!

[@serhiypidkuyko4206]

Hi Tushar Thank you for your video Some thoughts: 1.it's much more easier to think of current palindrome in terms of "center" + "radius" than of "length" 2.you don't need to analyse current palindromes after index=11of the input string (symbol "b") because for the indices >=12 the length of current palindrome is

[@joyoptimal6286]

At 3.21, at index 6. 'a' expands and is a candidate for center? No palindrome can be formed with characters to either side of 'a' at index 6. Can you clarify? Looks like you aren't answering any questions people have asked you below in comments.

[@nagalakshmichithambaranath1147]

Man, you are so fast.. the four rules you have written on board, you could have made it in less speed to understand the concept. Thanks for the video!

[@YeGaogaosanyong]

Very nicely explained. Thanks! It would've been even better if you could put up some code as well.

[@igordemura]

Good explanation, Tushar. But when you have sample with red marker, you need to put last 9 in place of 5.

[@shaluagarwal6771]

pLEASE be more clear in your explanations:-(

[@sandeepvulluri8887]

*explanation ma'am!

[@akashbhadouria6727]

@@sacchitjaiswal7896 chutiye sale

[@harris7963]

@@sandeepvulluri8887 wrong! *explanations

[@lostmeme9862]

When I asked why I was rejected from the entry level position at Panasonic for 60k a year full time I was told it was because I did not come up with an O(n) time complexity for this problem. I was given 1 hour.

[@JonathanBarrios2239]

Just wondering when do you start to ask the question what could be my next center?

[@hritikjoy8514]

Nice explaination Tushar :) u made it easy

[@fracturedude]

great explanation!

[@LetsBeHuman]

0:22 - how cells 8,9,10 (a,b,b) is a palindrome?

[@sukhmeetsingh5421]

Bhool ho jati hai yun taish mein aya na karo, let's be human alright!

[@rituagrawal2218]

I have got a ques. At time 6:00 in the video, We got max palidrome length as 9 at index 5; going any further can't give us any palidrome greater than this. I think we can stop there. This can be a optimization done in above algo. Tushar, let me know if I am wrong.

[@paramagurug9237]

It is difficult to do this optimization, there are chances with best cases it will be helpful. Consider the same example with little modification - "c b a x a b a x a b a x a" with b as center (position 6) the palindrome is 9, but when you move to position 8 (x as center) then the palindrome will be 11.

[@vineetkasat]

Guess you were not prepared to present this algorithm

[@ATXpert]

can I do it just using a stack? start from the left pushing and popping when I need, I think it could be done in O(n)

[@ayondas3449]

Generally your videos are good but I could not understand the explanation for this one. It will be great if you can create another video for Manacher's.

[@PyThon253]

Would it not be 1st=1 central 'a' [a], 2nd=3 central 'b' [a,b,a], 3rd=5 central 'a' [a,b,a,b,a]?? It seems you have many errors in your explanation.

[@purushottamparakh5165]

Subtitles : hello my name is too sharp 😊

[@tusharbudhe357]

How abb is palindromic ? Please correct if I am wrong.It's from index 8 to 10.

[@bgokhale]

How does it make it O(n)? Very act of finding a palindrome on either side of an index you are potentially going n indices. What am I missing?

[@siobhanahbois]

Each palindromic checks has an O(1) time complexity, so the total complexity is O(n).

[@raghavendrasinghchouhan17]

Bro its not O(N) even for odd case.. i feel . Can you pls answer this.. because going though particular index again we to expand for palindrome. What about that?.. then for even complexity will increase

[@jayantisswani]

Does finding the palindrome around each index not increase the time complexity? If this were so, why wouldn't the naive method have the same complexity?

[@surajsongire3954]

The last string was supposed to be even length, but it was odd length

[@_perspective_]

palindromic string of even length *, it is correct

[@JEE-it8mx]

A lengthy algo!! man i keep forgetting this imp algorithm

[@tobeess]

I understood everything. /s

[@theworldstudy2199]

Why do you mark 3 last letters as a palindromic substring whereas they're not abb. At the 23d second of the video

[@prakharsaxena4938]

Generally your videos are too good expect this.

[@MadForCs16]

except*

[@KimuraSetsuna]

z b a x a b a x a b a I think his explanation in 7:40 is not necessary always correct....??? for the string I wrote above, picking the X will expand out of the bound.

[@xalizalizx]

Why is it O(2n) ? at 14:53

[@surendrapalSingh]

Thanks Tushar for such an awesome video !! I just have a query. why we need to preprocess the array in case there are even lenghted panlindromes?

[@mhelvens]

Because this algorithm is all about expanding from a center character, and even length palindromes do not have a center character.

[@jovanrumenic1607]

how was 0:23 palindromic?? xD

[@vibsh625]

"aba x aba" how was it not palindromic ?? xD

[@thiestmayank]

In second case the at 13th index it should be 9 no?? But did you took 5? Only this point i didn't get. Will you please enlighten?

[@vivek5562]

I was going through the code in github: Although there's a comment added //Mark newCenter to be either end or end + 1 depending on if we dealing with even or old number input int newCenter = end + (i%2 ==0 ? 1 : 0); with this code you are not taking $ to be the next center node, why?

[@mithunroy8599]

Ok! Now I got it :) Thanks Tushar

[@himanshugupta1291]

Very nicely explained. :)

[@ehabteima]

Very convoluted

[@rajmeghpara2985]

why at the position of 'b' we need to find NEXT CENTER ?? i just cant understand plz help me

[@studyonly6972]

In your code you set the new center according to i is even or odd ? why

[@kant.shashi]

be clear ..don't assume people coming to this video are just about to code

[@corepunch]

Dude says point "won't be our new center" after having calculated it's palindrome size of 5, no s** Sherlock

[@vidhikhathuria941]

9:30 palindrome around it will be 2 since there are two bs

[@shivamkumar-qp1jm]

I am confused about 1st point and 3rd point looks like same thing

[@arsh772]

really appreciate how you make logics so easily understandable

[@sumanghosh3541]

may I know at which point we need to pick a centre and start back ward calculation

[@xavier.antony]

I love your tutorials. Good initiative. Thank you for helping software engineers. At the sometime, sorry to say that you need to improve your teaching skills a bit.

[@amansharan2820]

Guys how to determine if it is even case or odd case as it depends on the length of the pallindrome and not length of the input array ? And to find length of the pallindrome we need to apply 0(n^2) algo someone kindly help me how to determine even n odd.

[@classicmusic2672]

hello you videos are great please can you please solve this one: define an algorithm to find longest balanced sub-string of a certain string of packets and parenthesis

[@gauravkataraGK]

some concept that which center to pick was not clear

[@dayakar7234]

Nice work ! Thank you !