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!
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.
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!
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
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.
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.
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.
+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).
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.
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)
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.
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
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?
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.
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.
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.
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.
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.
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.
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
very good initiative to explain these concepts to us ... i always liked ur videos especially on BIT ... If possible post videos on suffix array + Lcp by o(n) (without suffix trees) ... just goes over my head ... thanks
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
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.
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 ?
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).
@@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.
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
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
It seems you were in hurry to end the video as soon as possible, generally your videos are good with nice explanation.But i'm totally confused with this one! Please try to explain it further if possible, as it is a complex topic try to explain the logic as simply as possible.Thank You.
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.
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?
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
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.
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
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);
Normally your videos are very clear but this wasn't one of them.
The algorithm was a bit complex, he did his best, i am sure!
Yes
me too, lol
At first I thought this is not clear but as I went through videos by others I found this one the best.
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!
subtitles: hello friends my name is too sharp 😂😂😂
Way better than all written tutorials for manachers!!! this was amazing
As always, concise, accurate, and easy to understand explanation of a rather tricky algorithm.
LOL cOnCiSe
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.
And the Oscar goes to Tushar Roy XD
Best tutorial on this algorithm! Very well explained and with examples!! Thank you!
Why is the runtime complexity O(n)? Could you elaborate more on that topic?
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.
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!
wow, it was so hard to explain yet you did. Thanks
The clearest explanation of Manacher's algorithm I've ever seen!!! Thanks a lot!!!
Tushar you have explained Manacher's better than anyone !
The explanation was great. Appending '$' in between every character to make it an odd length string was an interesting idea to reduce the code.
Thanks! Super clear. I finally understand Manacher's algorithm.
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
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.
A very tough concept explained better than most other people out there! A great effort. Thank you for this video.
Explaination was very clear and i understood this in the first watch itself. Thanks Tushar.
read some webpages but can't understand. your video really help
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.
This video really helped me in understanding this algorithm... Keep up the good work!
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.
+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).
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.
@@EmmaBostian what if you run it n times? O(nn) = O(n) or O(n^2)
@@shreyas6589 The right edge will never exceed the length of the string. So the inner loop will only run at most n times.
you explained it perfectly
Thank You Tushar Sir for great Explanation
this was clearly the only video till now that totally messed up!!!
really appreciate how you make logics so easily understandable
thanks Tushar saved my hours on hanging out the same explainatory stuff on the web
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)
Incredible explanation... WOW!!!!
nice explanation...especially the 4 cases for centre selection
finally understood this complex algo, but not completely its time complexity .
At 14:28, I think you want to put 9 corresponding to 'x' rather than 'a'.
Thanks for the video. very well explained !
since when is "abb" a palindromic substring?? what am i missing here? ... 0:21
He obviously meant to select 'bb'. Small error.
its really though ...but i belived in tushar and watched twice and now i get it ...thanks man
Subtitles : hello my name is too sharp 😊
your videos are amazing. keep up the good work.
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.
Thanks a lot Tushar sir !!!
Very convoluted
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
pLEASE be more clear in your explanations:-(
*explanation ma'am!
@@sacchitjaiswal7896 chutiye sale
@@sandeepvulluri8887 wrong! *explanations
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?
Thanx Tushar made my life easy bro...
NICE I don't know why people dislike your video
*That what happens when you memorize algos* LMFAO!!!
U mean tushar sir memorize them? ?
Agreed, where can I find the explanation. Any resources would you like to share
@@faizanurrahman6046 just search with the problem name.. you will find many youtubers
Very nicely explained. Thanks! It would've been even better if you could put up some code as well.
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.
Generally your videos are too good expect this.
except*
great explanation!
I understood everything. /s
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 ?
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.
Good explanation, Tushar. But when you have sample with red marker, you need to put last 9 in place of 5.
Nice explaination Tushar :)
u made it easy
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.
thank you so much
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.
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.
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.
Thanks a lot!
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.
it really cleared lots of doubts which i had before watching this video. thanks for clearing the base concepts behind the algo.
Ok! Now I got it :) Thanks Tushar
how was 0:23 palindromic?? xD
"aba x aba" how was it not palindromic ?? xD
sir , you are awesome :)
How abb is palindromic ?
Please correct if I am wrong.It's from index 8 to 10.
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.
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
very good initiative to explain these concepts to us ... i always liked ur videos especially on BIT ... If possible post videos on suffix array + Lcp by o(n) (without suffix trees) ... just goes over my head ... thanks
Just wondering when do you start to ask the question what could be my next center?
Nice work ! Thank you !
very helpful, thanks
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!
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
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.
Very nicely explained. :)
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 ?
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.
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).
@@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.
At 14:30 you are supposed to replace 5 with 9.
your are very good teacher. Thank you for efforts.
thanks a lot!
Why do you mark 3 last letters as a palindromic substring whereas they're not abb. At the 23d second of the video
0:22 - how cells 8,9,10 (a,b,b) is a palindrome?
Bhool ho jati hai yun taish mein aya na karo, let's be human alright!
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 ?
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
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
It seems you were in hurry to end the video as soon as possible, generally your videos are good with nice explanation.But i'm totally confused with this one! Please try to explain it further if possible, as it is a complex topic try to explain the logic as simply as possible.Thank You.
I am confused about 1st point and 3rd point looks like same thing
Tushar! Love your video. But this algorithm is too hard for me.................
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?
Because this algorithm is all about expanding from a center character, and even length palindromes do not have a center character.
The last string was supposed to be even length, but it was odd length
palindromic string of even length *, it is correct
11:01 didn't understand exactly why at this point we pick a new centre, can somebody please explain the reasoning?
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.
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?
In this case it's because you're reusing information thus not fully expanding every time.
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?
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
Why is it O(2n) ? at 14:53
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.
why at the position of 'b' we need to find NEXT CENTER ?? i just cant understand plz help me
Guess you were not prepared to present this algorithm
My mind exploded
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
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);
can you explain this part clearly?
some concept that which center to pick was not clear