Given a string, find longest palindromic substring in this string in linear time. github.com/mission-peace/inte... github.com/mission-peace/inte... / tusharroy25
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.
Hi, Tushar, thanks for the video. it is very helpful. May I have a question? In your first example, after you located the b at index 5, a Palindromic substring of length 9 obtained. Then you exclude the a at index 6. Afterwards can you just stop checking, it is because if the index at 7 will be another center of a palindromic substring, the max possible length would be 7. (even at index 6, we can give up since the possible longest substring would be 9, of course, unless we have to return all the longest palindromic substrings)
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.
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.
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.
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
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.
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
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?
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?
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!
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 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?
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.
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
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)
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
Very good explanation! In 11:02, could you please explain using what case you picked 'X' as center of the new palindrome? Also could you do videos on 1D and 2D peak finding?
In the example : a b a x a b a - first a (no palindrome therefore 1), then b is the center (with "a b a" as palindrome), then a (is the right edge of the current center b, so it's not the new center), next is x (which goes beyond the right edge of the current palindrome, therefore choose x as the new center with value 7).
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.
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.
How do u calculate the palindrome length.your getting one for the first character when it should be zero ,because it has no further left but right.Explain ourself.
+Tushar Roy I am unable to follow the video around 6:30 mins, when we chose value of 5 when comparing with 7. Still stumbling on that point. And also wondering if its O(n) since we are still scanning for lot of centers. Any tips would be appreciated.
+Tushar Roy why: (2 * (end - j) + 1) in the condition, is it always true that its a pallindrome with everything between j and end ? T[j] = Math.min(T[i - (j - i)], 2 * (end - j) + 1);
Nevermind, Got it !! Thanks for the tutorial. Also , If we change (2 * (end - j) +1) to (2 * begin - (i - (j - i))) +1 it is more intuitive articles.leetcode.com/wp-content/uploads/2011/11/palindrome_table5.png
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?
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.
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.
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.
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
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
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.
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.
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
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!
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.
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.
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
And the Oscar goes to Tushar Roy XD
This video really helped me in understanding this algorithm... Keep up the good work!
thanks Tushar saved my hours on hanging out the same explainatory stuff on the web
Best tutorial on this algorithm! Very well explained and with examples!! Thank you!
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 ?
may I know at which point we need to pick a centre and start back ward calculation
The clearest explanation of Manacher's algorithm I've ever seen!!! Thanks a lot!!!
Hi, Tushar, thanks for the video. it is very helpful.
May I have a question?
In your first example, after you located the b at index 5, a Palindromic substring of length 9 obtained.
Then you exclude the a at index 6. Afterwards can you just stop checking, it is because if the index at 7 will be another center of a palindromic substring, the max possible length would be 7. (even at index 6, we can give up since the possible longest substring would be 9, of course, unless we have to return all the longest palindromic substrings)
subtitles: hello friends my name is too sharp 😂😂😂
Just wondering when do you start to ask the question what could be my next center?
your videos are amazing. keep up the good work.
The explanation was great. Appending '$' in between every character to make it an odd length string was an interesting idea to reduce the code.
Thank You Tushar Sir for great Explanation
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.
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.
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.
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
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.
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
Nice explaination Tushar :)
u made it easy
11:01 didn't understand exactly why at this point we pick a new centre, can somebody please explain the reasoning?
wow, it was so hard to explain yet you did. Thanks
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?
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?
nice explanation...especially the 4 cases for centre selection
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!
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.
why at the position of 'b' we need to find NEXT CENTER ?? i just cant understand plz help me
Tushar you have explained Manacher's better than anyone !
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?
Thanks! Super clear. I finally understand Manacher's algorithm.
read some webpages but can't understand. your video really help
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.
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
Explaination was very clear and i understood this in the first watch itself. Thanks Tushar.
How is palindrome at array[14] length 9?
Nice work ! Thank you !
Good explanation, Tushar. But when you have sample with red marker, you need to put last 9 in place of 5.
In your code you set the new center according to i is even or odd ? why
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?
Each palindromic checks has an O(1) time complexity, so the total complexity is O(n).
Thanx Tushar made my life easy bro...
Very nicely explained. Thanks! It would've been even better if you could put up some code as well.
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)
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
really appreciate how you make logics so easily understandable
Thanks a lot Tushar sir !!!
Very nicely explained. :)
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!
Ok! Now I got it :) Thanks Tushar
A very tough concept explained better than most other people out there! A great effort. Thank you for this video.
Very good explanation!
In 11:02, could you please explain using what case you picked 'X' as center of the new palindrome?
Also could you do videos on 1D and 2D peak finding?
In the example : a b a x a b a - first a (no palindrome therefore 1), then b is the center (with "a b a" as palindrome), then a (is the right edge of the current center b, so it's not the new center), next is x (which goes beyond the right edge of the current palindrome, therefore choose x as the new center with value 7).
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.
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.
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.
How abb is palindromic ?
Please correct if I am wrong.It's from index 8 to 10.
Would you consider this algorithim to be following the concept "dynamic programming"?
I feel like this is more similar to sliding window tbh
How do u calculate the palindrome length.your getting one for the first character when it should be zero ,because it has no further left but right.Explain
ourself.
+Tushar Roy I am unable to follow the video around 6:30 mins, when we chose value of 5 when comparing with 7. Still stumbling on that point. And also wondering if its O(n) since we are still scanning for lot of centers. Any tips would be appreciated.
+Tushar Roy why: (2 * (end - j) + 1) in the condition, is it always true that its a pallindrome with everything between j and end ?
T[j] = Math.min(T[i - (j - i)], 2 * (end - j) + 1);
Nevermind, Got it !!
Thanks for the tutorial.
Also , If we change (2 * (end - j) +1) to (2 * begin - (i - (j - i))) +1 it is more intuitive
articles.leetcode.com/wp-content/uploads/2011/11/palindrome_table5.png
can you explain this part???
how was 0:23 palindromic?? xD
"aba x aba" how was it not palindromic ?? xD
finally understood this complex algo, but not completely its time complexity .
it really cleared lots of doubts which i had before watching this video. thanks for clearing the base concepts behind the algo.
its really though ...but i belived in tushar and watched twice and now i get it ...thanks man
great explanation!
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.
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?
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.
NICE I don't know why people dislike your video
very helpful, thanks
Incredible explanation... WOW!!!!
this was clearly the only video till now that totally messed up!!!
Subtitles : hello my name is too sharp 😊
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.
your are very good teacher. Thank you for efforts.
some concept that which center to pick was not clear
since when is "abb" a palindromic substring?? what am i missing here? ... 0:21
He obviously meant to select 'bb'. Small error.
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.
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.
I am confused about 1st point and 3rd point looks like same thing
sir , you are awesome :)
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)
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.
What about even length palindrome
ye video samjha nhi raha but bata raha hainkya hua.
Why is it O(2n) ? at 14:53
Very convoluted
Thanks a lot!
At 14:28, I think you want to put 9 corresponding to 'x' rather than 'a'.
Thanks for the video. very well explained !
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
Generally your videos are too good expect this.
except*
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
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.
thank you so much
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
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.
The last string was supposed to be even length, but it was odd length
palindromic string of even length *, it is correct