# Longest palindromic string

Published on

### 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, is xabax and palindrome? Similarly is xabay 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 and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(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)
};

If you think somebody would benefit from reading this post, please share away and help me reach more people.

• Tags :
• leetcode
• javascript
• longest palindrome substring
• dynamic programming
• Keywords :
• leetcode
• javascript
• longest palindrom substring
• dynamic programming
• interview questions