Write a program to find the longest Palindrome in a string
Problem
Given a string s, return its longest substring that is a palindrome. If several have the same length, return any one of them (commonly the first).
Example 1
Input: "babad" Output: "bab"
"aba" is also correct.
Example 2
Input: "cbbd" Output: "bb"
Also asked as: longest palindromic substring
Test cases
Case 1
Input: "babad" Expected (any of): ["bab","aba"]
Case 2
Input: "cbbd" Expected (any of): ["bb"]
Case 3
Input: "a" Expected (any of): ["a"]
View solutionHide solution2 approaches
1. Expand around center
Time O(n²)Space O(1)
Every palindrome has a center (a char, or a gap between two chars). Expand outward from all 2n−1 centers.
function longestPalindrome(s) { let best = ''; const expand = (l, r) => { while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; } return s.slice(l + 1, r); }; for (let i = 0; i < s.length; i++) { for (const p of [expand(i, i), expand(i, i + 1)]) if (p.length > best.length) best = p; } return best;}2. Dynamic programming
Time O(n²)Space O(n²)
dp[i][j] = s[i]===s[j] && dp[i+1][j-1]. Fill by substring length. Same time, O(n²) space, easier to reason about.
function longestPalindrome(s) { const n = s.length; const dp = Array.from({ length: n }, () => Array(n).fill(false)); let start = 0, maxLen = 1; for (let i = 0; i < n; i++) dp[i][i] = true; for (let len = 2; len <= n; len++) { for (let i = 0; i + len - 1 < n; i++) { const j = i + len - 1; if (s[i] === s[j] && (len === 2 || dp[i + 1][j - 1])) { dp[i][j] = true; if (len > maxLen) { start = i; maxLen = len; } } } } return s.slice(start, start + maxLen);}Manacher’s algorithm solves this in O(n) but is rarely expected in interviews — mention it exists.