# 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 (e**xpand 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 “ba**b**ad” 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 “c**bb**d” 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 thestartindex 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

**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:**