Question
Given a string s
, return the longest palindromic substring in s
.
Example 1:
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Example 3:
Input: s = "a"
Output: "a"
Example 4:
Input: s = "ac"
Output: "a"
Constraints:
- <= s.length <= 1000
s
consist of only digits and English letters (lower-case and/or upper-case),
Hints
- How can we reuse a previously computed palindrome to compute a larger palindrome?
- If
aba
is a palindrome, isxabax
and palindrome? Similarly isxabay
a palindrome? - Complexity based hint: If we use brute-force and check whether for every start and end position a substring is a palindrome we have
O(n^2)
start - end pairs andO(n)
palindromic checks. Can we reduce the time for palindromic checks toO(1)
by reusing some previous computation ?
Solution
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
const len = s.length;
const dp = [];
let i = 0;
let maxLength = 0;
let substrStart = 0;
// All substrings of length 1 are palindromes
while (i < len) {
dp[i] = [];
dp[i][i] = true;
i++;
}
maxLength = 1;
// All substrings of length 2 are palindromes if both characters are same.
i = 0;
while (i < len - 1) {
if (s[i] == s[i + 1]) {
dp[i] = dp[i] || [];
dp[i][i + 1] = true;
substrStart = i;
maxLength = 2; // Atleast one palindromic substring of length 2 is found
}
i++;
}
let substrLength = 3;
while (substrLength <= len) {
i = 0;
while (i < len - substrLength + 1) {
let j = i + substrLength - 1; // index of the position where a substring of length "substrLength" ends.
if (s[i] == s[j] && dp[i + 1][j - 1]) {
dp[i] = dp[i] || [];
dp[i][j] = true;
if (substrLength > maxLength) {
maxLength = substrLength;
substrStart = i;
}
}
i++;
}
substrLength++;
}
return s.substr(substrStart, maxLength)
};