Write a program to find the longest Palindrome in a string

Medium

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"]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.