There are a lot of videos talking about this Longest Palindrome Substring question, but there are still some details that took me awhile to figure it out. I broke it down a little so we can understand the approach better. I also included some explanations on the calculations.
How to find a palindromic substring (expand around center)
Starting from the center of a substring to evaluate wether the substring is a palindrome. If the letter on the left side of the center
s[center-1] equals the letter on the right side of the center
s[center+1], we keep moving to the next letter on each side, until we hit unequal:
s[center - 1] === s[center + 1]
s[center - 2] === s[center + 2]
... === ...
s[center - n] === s[center + n]
s[center - n -1] !== s[center + n + 1]//exit
Then we find
There are two scenarios for center(s) in a string:
- there is only one center
s[i]in a palindrome when its length is odd: the center of “babad” is “b” at index 2
- there are two centers
s[i+1]in a palindrome when its length is even: the centers of “cbbd” are “b” at index 1 and “b” at index 2
We do not know which kind of strings we are getting, so we need to include both scenarios.
Code and explanation
I set a function called
findLPS(s, center1, center2) that takes the string we are evaluating, and both centers. In the function there are two variables
right to track the start and end indexes of the substring. While
right are in bounds and
s[left]===s[right] we keep moving
left to the left and
right to the right. When the condition was not satisfied we break out of the while loop and return the length of the substring
Why the length of the substring is
For example, when s is “aba”, left and right start at index 1, thenleft--, left = 1, 0, -1right++, right = 1, 2, 3When we break out of the while loop, left is -1 and right is 3. We need to move back an index on both sides:substring.length = (right-1)-(left+1)+1= (3–1)-(-1+1)+1 = 3which equals to right-left-1 = 3-(-1)-1 = 3
In the longestPalindrome function, I used a for loop to evaluate each letter in the string to see wether it is the center of a palindrome, as mentioned before, we need to include both scenarios of the center(s). If
len is longer than
longest we can assign
longest and start to calculate
end indexes of the longest palindromic substring we want to return.
Why start is
i - Math.floor((len -1)/2) not
i — Math.floor(len/2)?
For example, i is at the center of the palindrome and we want to calculate the start index of the string:"aba", i = 1, len = 3
i - Math.floor(len/2) = 1 - 1 = 0
i - Math.floor((len-1)/2) = 1 - 1 = 0"cbbc", i =1, len = 4
i - Math.floor(len/2) = 1-2 = -1 //index out of bounds
i - Math.floor((len-1)/2) = 1 - 1 = 0 //index in the boundsWe are dealing with indexes here, when the length of the returned substring is even and the centers are i and i+1. We are using i to calculate the start and end indexes. Use "cbbc" again:c b b c
0 1 2 3i = 1
len = 4
len/2 = 2
Math.floor((len-1)/2) = 1We can see that i is "closer" to the start index than to the end index. So for end index we do not need to minus one off the len:
end = 1 + Math.floor(4/2) = 3
start = i - Math.floor((len-1)/2) = 0
Time complexity : O(n²). Since expanding a palindrome around its center could take O(n)time, the overall complexity is O(n²).
Space complexity : O(1).