Longest Palindromic Substring

The key idea

Every palindrome has a center, so there are only 2n-1 possible centers (n single chars plus n-1 gaps between chars). Expand outward from each center while the two characters match; the widest expansion is the answer. This sidesteps checking all O(n^2) substrings explicitly.

Problem

Given a string s, return the longest palindromic substring in s.

A palindrome is a string that reads the same forward and backward. A substring is a contiguous, non-empty sequence of characters inside s. If several substrings tie for the longest length, returning any one of them is accepted.

Constraints

1 <= s.length <= 1000
s consists of only digits and English letters.

Examples

Input: s = "babad" Output: "bab"

Input: s = "cbbd" Output: "bb"

Complexity

Time: O(n^2) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →