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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Longest Palindromic Substring and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →