Longest palindromic substring

Question

Given a string, return the longest contiguous substring that reads the same forwards and backwards.

"babad"   -> "bab"      # "aba" is equally valid
"cbbd"    -> "bb"
"a"       -> "a"

Return any one longest palindromic substring. The brute force, check all $O(n^2)$ substrings at $O(n)$ each, is $O(n^3)$ ; aim for $O(n^2)$ .

Accepted Answer

Every palindrome has a center: a single character (odd length) or a gap between two characters (even length), 2n - 1 centers in total. From each center, expand outward while the two frontier characters match; each expansion step is O(1), and matching stops the growth. Track the best interval seen. The classic bug is forgetting even-length centers: "cbbd" has no odd-centered palindrome longer than 1, so missing the (i, i+1) centers returns the wrong answer. Tracing "babad": center 1 (the first a) matches s[0] == s[2], then hits the left edge, returning indices (0, 2)-"bab", length 3. Center 2 …

Longest palindromic substring

Your answer

More Coding questions