 # Longest Palindromic Substring in JavaScript

## Problem

Given a string `str`, find the longest palindromic substring in `str`.

Example 1:

``````Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
``````

Example 2:

``````Input: "cbbd"
Output: "bb"
``````

## Things to know

### What is palindrome?

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam or racecar or the number 10801.
-- wikipedia

To sum up, madam and maddam both are valid palindrome. It is because the word will be the same even if we reverse it. Pay attention to the middle characters; one `d` and the other one is two `d`. They still are valid palindrome.

## Approach

We going to iterate each character in the `str`; and within that character, we expand and look for the longest palindrome. As we keep iterating, we only keep the longest palindrome.

Since we need to look for the longest palindrome substring, we no longer need to check whether or not the string is a valid palindrome. Instead, we need to create a helper method `expandAroundCenter` that return the longest palindrome of given two middle indices from a string. We need two indices beacause we know the length of the palindrome can be even and odd. For instance, `madam` and `maddam` both are valid palindrome.

## Expand Around Center

``````
/**
* @param {string} str
* @param {number} left
* @param {number} right
* @return {number}
* @time complexity: O(n)
* @space complexity: O(1)
*/
var expandAroundCenter = (str, left, right) => {
while (left >= 0 && right < str.length && str.charAt(left) === str.charAt(right)) {
left--;
right++;
}
return right - left - 1;
};
```
```

This method accepts three parameters: `str`, `left`, `right`. `str` is the string that we are going to test against with. `left` is the index position of the `str`, it will be decrement each time we expand the range. `right` is the index position of the `str`, it will be increment each time we expand the range.

Inside the method, we do a while loop. The condition would be while the left and right index position are within the boundary of the string and the most outer left character match the most outer right character. It will expand the range; decrement the left index and increment the right index.

In the end, it will return the length of the range.

We are going test this method with a string `abcbbca`. One thing we need to know is that. There are two palindrome within this string. They are `bcb` and `cbbc`; they both are valid palindrome.

If we call this method `expandAroundCenter('abcbbca', 2, 2)`, it will return `3`. It is because `bcb` is the largest palindrome. However, if we try `expandAroundCenter('abcbbca', 3, 4)`, it will return `4`; `cbbc` is the longest palindrome is this case.

``````
describe('expandAroundCenter', () => {
it('should return 1', () => {
assert.strictEqual(expandAroundCenter('abcbbca', 2, 2), 3);
});

it('should return 4', () => {
assert.strictEqual(expandAroundCenter('abcbbca', 3, 4), 4);
});
});
```
```
``````  expandAroundCenter
✓ should return 1
✓ should return 4

2 passing (8ms)
``````

## Largest Palindromic Substring

``````
/**
* Return the length of longest substring
*
* @param {string} str
* @return {string}
* @time complexity: O(n2)
* @space complexity: O(1)
*/
var longestPalindromeSubstring = (str) => {
if (str === undefined || str === null || str.length < 1) {
return '';
}

let start = 0;
let maxLen = 0;

for (let i = 0, l = str.length; i < l; i++) {
let len1 = expandAroundCenter(str, i, i);
let len2 = expandAroundCenter(str, i, i + 1);
let len = Math.max(len1, len2);

if (len > maxLen) {
maxLen = len;
start = i - Math.floor((len - 1) / 2);
}
}

return str.substr(start, maxLen);
};
```
```

It iterates each character in the string and call the helper method that we just created earlier.

## Solution

``````
/**
* Return the length of longest substring
*
* @param {string} str
* @param {number} left
* @param {number} right
* @return {number}
* @time complexity: O(2)
* @space complexity: O(1)
* @example
* expandAroundCenter('abcdefg', 3, 3) => 1
* expandAroundCenter('abedefg', 3, 3) => 3
* expandAroundCenter('abeddefg', 3, 4) => 4
*/
var expandAroundCenter = (str, left, right) => {
while (left >= 0 && right < str.length && str.charAt(left) === str.charAt(right)) {
left--;
right++;
}
return right - left - 1;
};

/**
* Return the length of longest substring
*
* @param {string} str
* @return {string}
* @time complexity: O(n2)
* @space complexity: O(1)
* @example
* longestPalindromeSubstring('cbbd') => 'bb'
*/
var longestPalindromeSubstring = (str) => {
if (str === undefined || str === null || str.length < 1) {
return '';
}

let start = 0;
let maxLen = 0;

for (let i = 0, l = str.length; i < l; i++) {
let len1 = expandAroundCenter(str, i, i);
let len2 = expandAroundCenter(str, i, i + 1);
let len = Math.max(len1, len2);

if (len > maxLen) {
maxLen = len;
start = i - Math.floor((len - 1) / 2);
}
}

return str.substr(start, maxLen);
};
```
```

## Test Case

``````
const assert = require('chai').assert;

describe('Longest Palindromic Substring', () => {

it('should return \'aba\' when \'babad\' is given', () => {
});

it('should return \'bb\' when \'cbbd\' is given', () => {
assert.strictEqual(longestPalindromeSubstring('cbbd'), 'bb');
});

});
```
```
``````  Longest Palindromic Substring
✓ should return 'aba' when 'babad' is given
✓ should return 'bb' when 'cbbd' is given

2 passing (8ms)
`````` Mike Mai   Brooklyn, New York
I am full-stack web developer, passionate about building world class web applications. Knowledge in designing, coding, testing, and debugging. I love to solve problems.