Skip to main content

5. Longest Palindromic Substring

medium

Return the longest palindromic substring of a string. The standard expand-around-center solve runs in O(n^2) time with constant extra space — Manacher's is O(n) but rarely required.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

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

Examples

Example 1

Input
s = "babad"
Output
"bab"

Explanation: "aba" is also a valid answer.

Example 2

Input
s = "cbbd"
Output
"bb"

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute-force checks every substring for palindromicity: O(n^3). Too slow even for n = 1000.

Hint 2

Every palindrome has a center. There are 2n - 1 candidate centers: each character (odd-length palindromes) and each gap between characters (even-length palindromes).

Hint 3

For each center, expand outward while characters match. Track the start/length of the longest palindrome found.

Solution approach

Reveal approach

Expand around center. Iterate i from 0 to n-1; for each i, try expanding as an odd-length palindrome centered at i, then as an even-length palindrome centered between i and i+1. The expand helper takes left and right pointers and walks outward while they're in bounds and s[left] == s[right]; returns the resulting length. Track the (start, end) of the longest seen and return s.substring(start, end+1). O(n^2) time, O(1) extra space. Manacher's algorithm gets this to O(n) but is rarely required in an interview.

Complexity

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

Related patterns

  • dynamic-programming
  • expand-around-center

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta
  • Bloomberg

More Strings practice problems

See all Strings problems →