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('babad') => 'bab'
* 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', () => {
assert.strictEqual(longestPalindromeSubstring('babad'), 'bab');
});
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)
