Longest Palindromic Substring O(N) Manacher's Algorithm

hi everyone this is variance reform I deserve today I am going to talk about longest palindromic substring in order of M using managers algorithm so given a string s we need to find out the longest panoramic substring in order of n for example if we have a string like this a be a be a be a the longest palindromic substring of this is the whole string okay we have multiple palindromes here a be a be a be a be a and so on but we want to find out the longest palindromic substring okay we have already discussed the dynamic programming based solution for this particular problem which is order of n square please check that video out for now we will go ahead and discuss the most efficient algorithm for this which is based on which is managers algorithm other than dynamic programming there is another order of N squared algorithm where we expand around the center's to find out a parent room okay so each character is considered as the center and the gap between the characters is also considered as a center for even palindrome so for example we start with a we find out the parent term length for that then in between a and B then find out the palindrome length for that Center and so on we do that till the end once we have all the palindrome lengths we'll take the maximum of the palindrome length array and we'll know which is the largest palindromic substring but this is order of n square right because we are expanding at each Center that we encounter our goal is to go from order of n square to order of n using a few clever insights that manages algorithm uses the first insight is obviously expanding around the center's so if we consider a as the center and expand around it we will find a pair in term of only length one okay one character if we go ahead and put a center in between a and B we won't find a palindrome because a and B do not match okay given this as the center if we go ahead and consider B as the center we'll find a palindrome of length 3 the next Center is the empty space between B and a again the palindrome length is zero here if we consider a as the center we'll find a palindrome of length 5 if we go ahead to be will find a palindrome of length 7 now let's take a thinking pass current algorithm is order of n square we want to go to order of n what is hurting us expanding around every Center is hurting us what if we cut down the number of expansions we need to understand the concept of panderdome even better to do that let's assess our progress and see where we are at right now ok we have expanded all the center's all the way till B and we have lens for palindromes for each Center along the way considering a is the center we have a pendulum of length 1 and B is the center palindrome of length 3 a is the central upendra of length 5 ok and for the rest of the center's a B a we don't know the palindrome lengths right now I am omitting the centers in between the characters just for simplicity now let's just concentrate on this Center which is B 2nd last character and try to figure out its palindrome length by not expanding to do that we will look at the pen in room centered at this point in a different manner let's look at it in a different perspective like this what we see here is palindromes are symmetric at the center's that is the second insight that we are going to use ok since they are symmetric at the center's the left part of the palindrome looks exactly similar to the right part of the current row that is the definition of the palindrome right so that is what we are going to use to cut down our expansion ok so you see here every character on the left hand side is mirror on the right hand side since the characters on the left hand side of the left hand side are mirror images of the of the right hand side what we can do is we can directly copy the mirror mirror lengths towards the right side ok so what would be the length of the parent room here if you look at it without expanding just look at it don't execute an algorithm just look at it you see that at this point the palindrome length is 3 right and what is here at this point it is also 3 instead of expanding here where we have a question mark instead of expanding here we are directly copy the pendulum length from the mirror center to this Center okay let's look for this Center which is the last character what would be the length of the palindrome here one right we just copy from the mirror Center okay now for the character a here what will be the length of the pen in room five we just copied it from the mirror Center okay so are we done have you considered all the cases is reusing the pendulum length at Mirror Center enough or do we need more work have we reached order of n these are the questions that come to mind right the answer to all of these is no let's assess our progress again so we have a parent home center at this point of length seven which has a boundary here the left boundary and the right boundary here now suppose that this string can be extended from the left as well as from the right okay let's see where we are at without the extension without the extension we had the palindrome lengths of one at the first character three at the second character five and so on what if we had one more character after the right boundary now let's look at this whole string in a different perspective the question arises are the lengths that we copied from the mirror Center correct are the palindrome lengths correct I don't think so okay if you add one more character at the right boundary these lengths change so if you consider a as the center the actual panderdome length for a is the center is 3 which is greater than one it and if you consider B as the center it is definitely greater than 3 which is equal to 5 okay now let's take a thinking pause again the length of the center on the right hand side is greater than or equal to length of mirror it is not just equal to it is greater than or equal to so once you copy the length of the mirror you have to start expanding from the end of the 10th okay so basically once you have three you know that the parent term centered at B is at least of length three that's why we start comparing from the ends of that particular mirror length that we copied so we just compare B and B we don't compare any and then we get a length of five now let's jump on to the another case where we expand the left boundary instead of the right boundary and we know what character is after the left boundary let's switch this B here what happens now is the lengths on the Left centrist of the main center are greater than they were so for a here it expands beyond the left boundary for B it also expands beyond the left boundary to length five similarly for the center K but by the first rule we need to copy this lens towards the right side right are these lengths cut let's see considering a has the center we see that the Benedum lengths centered at a is five so it is at least five not seven similarly for parent ROM will centered at B it is at least three not five why is this happening because we never know what character would be after the right boundary we have to expand and look at it because palindrome is not symmetric beyond the boundaries it is only symmetric till the boundaries that's why the length of the palindromes at the right hand side are at least till the end of the bounder okay so how would we get this length we'll count the number of characters from the right end to the center including the including the empty spaces so what is the count from the right boundary till the center it is what which is basically the right boundary - ace index okay just bear with me for a moment it is this is little tricky okay and now for B how do we get three we count from the right boundary till the B's index which is basically R minus B's index and for a we have another empty space here right become that as well and is index we get our - is index equal to five okay now this this looks very abstruse right now imagine at this central the palindrome is folded okay a palindrome of length three is folded what you would say is if you fold at the center you will get B a a is placed on top of a here okay if it is folded you count the empty spaces as as well it will give you the length of the peridot at each Center how do we unfold and count the number of characters in the palindrome we just count from the right boundary including the empty characters okay that's how we know the least length of the palindromes on the right hand side centers okay so for this particular Center we have the count as one two three so that is the length of the folded palindrome if we unfold it we will see that it is a BA okay fold it a it will look like this unfold it it will look like this okay we are counting from the right boundary that's why we will have our - that particular center's index okay again in this case this length that we get which is right boundary - the Centers index is the minimum length that we have for that palindrome okay so basically we need to expand beyond that length okay now let's summarize whatever we learned in two simple rules okay assuming we are in this state where we found the palindrome of length seven and we are trying to find the length of the palindrome center right here and we know that the mirror is here what are the two rules if the length of the mirror here on the left hand side expands beyond the left boundary of the main palindrome what we are going to do is we are going to update the length of the parent ROM at this Center equal to R minus B's index the other case is if the length of the mirror here is within L what we are going to do is we are going to update the length of the palindrome at this question mark at B is equal to length of the mirror okay we just copied the length of the mirror here once you have once you know which case it is and update the length accordingly for the palindrome on the right hand side Center you will expand beyond that minimum length from one and two okay and that's how you find the actual length of the pendulum at that particular Center these are the three rules of managers algorithm that said that's that once you understand these three things the whole code is pretty easy okay let's go through the code of managers algorithm what we are going to do is we are going to transform this string into another string like this by adding hashes in place of n empty spaces just to consider the case of even length palindrome and we have some characters to demarcate the start and end of the string we also have an array which tracks the lengths of the pen in terms at each Center so here is the code for the managers algorithm let's go through it step by step we'll start with the second iteration where I is pointing here C is the center of the main pennant room R is the right boundary of the main palindrome and mirror is the mirror location for I I is basically we are trying to look for another main pennant room and we are trying to find next Center for the next main palindrome okay so if the lengths of the parent room that we find at I as the center expands beyond the main palindrome center at C will shift C to I as we go along you see how C is updated how I is updated how I is trying to find the new center and stuff like that so let's go ahead in the next iteration I moves forward considers a as the center okay so first step is before even expanding it we try to find out the mirror for that Center okay so what is the mirror for i considering C as the center of the main pennant row it will be 2 C minus okay if you work it out you'll understand that for c4c as the center mirror for I would be 2 into C minus I okay once we have the mirror the next step is to see if I lies within the boundary of the main pennant oh okay does I live within our no right so we can't apply two rules that we discussed about updating the least palindrome lengths from Panda mirror or updating it from the right boundary which is basically our minus I or P of mirror okay we can't do that because it doesn't lie within the boundary of the main pended okay so this case fails next step is to try to expand by comparing the characters around the center okay so we see that the characters match so the length of the palindrome center net eye which is a increases right which is which becomes 1 then we try to expand again by considering this these characters okay but these characters do not match so we move on to the next condition now since I has moved beyond the main palindrome which is centered at C we move C to I okay so basically the pennant term centered at I plus the palindrome length at I if it is greater than the right boundary of the main pennant room which is our we shift the center C to I okay we shifted the center here to one because I expanded beyond the main palindrome since we shifted C we have to shift the right boundary of the main pen room because main palindrome has moved out now right okay so by now you you might have understood that I is trying to find the next center of the main pen room and C is the main pendulum that that is into consideration right now okay so let's move on to the next Center that we aren't we want to consider as the main palindrome so I move here as soon as I moves we figure out where the mirror is okay in the hope that we would be able to copy the mirror length to I and expand beyond that okay but does I live within the boundary of the main toilet palindrome no right it doesn't like it lies on the boundary it should be within the boundary okay since it doesn't lie within the boundary we can't follow the two rules that we discussed before in the earlier slides okay so we'll try to expand anyway here we try to expand and see that the characters around I which is a and B do not match does the pen drum center that I expand beyond are no right so let's move on to the next Center next enter is be the mirror for this would would have been this character okay we don't care about it because I is anyway not inside the main parent or now we we definitely have to end up expanding okay so while expanding we compare these characters these characters are similar and that's why we increment the count of the length of the parent or it becomes one okay we expand further compare a and a and we see that they match that's why we expand the parent room again and say that the pendulum is of length two then we try to match the next two characters and we see that they match and again we increment the counter okay so we have found a parent room of length three now again we try to expand and we see that there is a mismatch between those characters B and dollar okay so the current condition becomes false and we move ahead to check the next condition next condition is does the parent ROM Center that I expand beyond the main panel obviously it does right so we have to move the center of the main pen room from C to fine so we move it here okay and accordingly are also moves ahead now we will also have a left boundary we don't track the left boundary in the code but for the sake of understanding I am putting the left boundary for the main pen room now let's move I to the next Center into consideration and for this particular Center we have mirror at this point okay now since I lies within the boundary of the main tandem we can definitely copy the palindromes lengths at mirror which is of length zero so we copied the parent of length from here to here this is zero it doesn't make much of a difference now once we copy that next thing we do is we try to expand while expanding we see that the characters around that Center do not match so we definitely won't increment the count right now the other question is is is the pennant roam at center eye expanding beyond our no right so we don't have to worry about it we don't have to shift the center's we still have the center at be here okay let's move on to the next enter into consideration now since I lies within the boundary of our we can definitely copy the mirror length here once we copy the mirror length we know that it is of at least this length so we have to expand beyond this length okay we'll try we won't compare hash and hash now we'll compare b and b so we compare b and b and we see that they are they are the same so the parent term expands so it becomes of length 2 and we try to expand it even further we find matching characters we expand it it becomes of length 3 try to expand it even further it becomes of length 4 and we expand it further it becomes of length 5 and then we try to match the next characters we see there is a mismatch now we move on to the next condition where we check if the parent am centered at I expands beyond the boundary are it does right it does expand beyond the boundary are so definitely we have to move the center to I right we move the center to I accordingly we move the right boundary to I plus P of I okay which is basically the boundary of the main pennant so let's move I to the next Center into consideration I comes here and then mirror is here so we copy the mirror length which is zero here and then we try to expand character mismatch so we skip it okay the next condition there where it doesn't expand beyond the beyond our there is no question of moving the main center let's move on to the next Center into consideration the mirror is here we copy the mirror length okay now we know param centered at I is at least of length three which is basically this okay so we have to expand beyond this length we we don't have to do redo the job of comparing these characters again we'll start expanding beyond this length by comparing b and b they match the pendulum length increases again we try to compare the next characters into consideration they match the next characters match and again they match we have a pendulum of length seven and then we try to match the last two characters we see that there is a mismatch okay the next question is does this parent on expand beyond the main palindrome that we had yes it does it expands beyond our so we move the center of the parent on here and we move the right boundary of the pen room here okay and then we start moving eye again to find the next sent next enter into consideration is here mirror is here we copy the mirror length which is zero we try to expand mismatch so we don't increase the pendulum length it doesn't expand beyond our so we don't move the center we move I a head okay and mirror is here we copy the mirror length which is 5 so we have palindrome of this length of 5 and then we try to expand beyond it we see that there is a mismatch and we can't increment the count does it expand beyond our no right so we don't move the center similarly for the next Center which we copy the length 3 we try to expand mismatch we don't move the centers similarly for all the centers on the right-hand side okay mirror is there and we copy the mirror length from here to here and we try to expand beyond it it doesn't expand it is a mismatch so we don't take smart and this paradigm centered at this point doesn't expand beyond our so we don't have to move the center and we have reached the end of the string that's the execution of managers algorithm please go through the code and let me know if you have any issues or doubts and about the complexity of this algorithm and give an overview of the explanation of complexity I will try to upload another video for the complexity because I don't think it's straightforward to explain right now and it will increase the length of the video so for the complexity here if you see once you have found a larger pan in room you just walk one by one to the end of the right boundary okay so in the worst case you will do two iterations of the string that's it you are not expanding every Center toward till the end of the swing right you are just walking once more to the end of the boundary so that is why it will amount to order of two often which is basically Auto fine okay thank you for watching the video I know it has been a long video thanks for staying patient also check out the references that I used for understanding this algorithm those references are in below in the description and also let me know if you have any doubts or questions in the comment section below and finally stay tuned and subscribe to the channel I deserve thank you

Channel: IDeserve

Views: 142,863

Keywords: Data Structures, Algorithms, Interview Questions, Computer Science, Programming Interview Questions, Technical Questions, Interview Answers, Algorithmic Questions, Algorithmic Answers, Programming Interview Questions and Answers, Longest Palindromic Substring, Manacher's Algorithm, Longest Palindromic Substring O(N), Dynamic Programming, Longest Palindromic Substring Example, coding, interview

Id: nbTSfrEfo6M

Length: 23min 48sec (1428 seconds)

Published: Thu Sep 03 2015