LeetCode 5 Expand Around Center Solution in Javascript

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.

Question:

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 finds.substring(center — n, center + n + 1) is a palindromic substring (javascript substring() end index is not inclusive, so we need to add one to capture the whole substring).

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] and 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 left and right to track the start and end indexes of the substring. While left and 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 right-left-1 .

Why the length of the substring is right-left-1 not right-left+1?

For example, when s is “aba”, left and right start at index 1, then
left--, left = 1, 0, -1
right++, right = 1, 2, 3
When 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 = 3
which 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 len to longest and start to calculate start and 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 bounds
We 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 3
i = 1
len = 4
len/2 = 2
Math.floor((len-1)/2) = 1
We 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

Complexity Analysis

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).

Resource: