The problem. Given a string s, return its longest substring that is a palindrome. If several have the same longest length, any one of them is accepted.
s = "babad" -> "bab" (or "aba")
s = "cbbd" -> "bb" (an even-length palindrome)
s = "forgeeksskeegfor" -> "geeksskeeg"This is the previous lesson with a different question: instead of counting every palindrome, remember the widest one. Grow from all 2n - 1 middles; each growth stops at the first mismatch, so where it stops tells you the widest palindrome with that middle.
There's also a classic table-based solution. A substring s[i..j] is a palindrome exactly when its end letters match and its inside s[i+1..j-1] is a palindrome — a small problem built from a smaller one, which is dynamic programming. It's worth knowing because the same table answers many related questions, but it costs O(n²) memory where expansion needs none.
Fill pal[i][j] for every pair, with i going from the end backwards so that pal[i+1][j-1] is always ready when it's needed. Substrings of length 1, 2 and 3 only need their ends to match.
function longestPalindrome(s) { const n = s.length; // pal[i][j]: is s[i..j] a palindrome? Its ends must match and its inside must be one. const pal = Array.from({ length: n }, () => new Array(n).fill(false)); let bestStart = 0, bestLen = 1; for (let i = n - 1; i >= 0; i--) { // i goes down so row i + 1 is ready for (let j = i; j < n; j++) { pal[i][j] = s[i] === s[j] && (j - i < 3 || pal[i + 1][j - 1]); if (pal[i][j] && j - i + 1 > bestLen) { bestStart = i; bestLen = j - i + 1; } } } return s.slice(bestStart, bestStart + bestLen);}Time O(n²), space O(n²). Every cell of the table is filled once in O(1). For n = 1000 that's a million booleans.
Each middle grows while its ends match; the widest growth so far stays green.
function longestPalindrome(s) { let bestStart = 0, bestLen = 0; const expand = (left, right) => { // grow outwards while the ends match while (left >= 0 && right < s.length && s[left] === s[right]) { left--; right++; } // The loop went one step too far on each side: the palindrome is s[left+1..right-1]. if (right - left - 1 > bestLen) { bestStart = left + 1; bestLen = right - left - 1; } }; for (let center = 0; center < s.length; center++) { expand(center, center); // odd length: one middle letter expand(center, center + 1); // even length: the gap after it } return s.slice(bestStart, bestStart + bestLen);}Time O(n²), space O(1). The same work as counting, plus two numbers to remember the best.
Expansion is the answer to give: as fast as the table, no memory, and easy to explain. (Manacher's algorithm reaches O(n) by reusing mirror information, but it's specialist knowledge.)
"cbbd" gives "bb"; skipping the gap centres misses it."racecar" returns itself.dp[i][j] from dp[i+1][j-1] + 2 when the ends match, else the better of dropping one end.