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

## 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`s.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, 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 `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 = 3i - Math.floor(len/2) = 1 - 1 = 0i - Math.floor((len-1)/2) = 1 - 1 = 0"cbbc", i =1, len = 4i - Math.floor(len/2) = 1-2 = -1 //index out of boundsi - 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 c0 1 2 3i = 1len = 4len/2 = 2Math.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) = 3start = 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: