Skip to main content

5. Longest Palindromic Substring

medium

Return the longest contiguous palindromic substring. Two clean approaches: 2D DP over (i, j) marking whether s[i..j] is a palindrome, or expand-around-center for O(n^2) time and O(1) space.

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 consist 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 is O(n^3): check each of the O(n^2) substrings for the palindrome property in O(n).

Hint 2

DP: dp[i][j] is true iff s[i..j] is a palindrome. dp[i][j] = (s[i] == s[j]) AND (j - i < 2 OR dp[i+1][j-1]).

Hint 3

Iterate by increasing length so dp[i+1][j-1] is already filled when you compute dp[i][j].

Hint 4

Expand-around-center is simpler: for every index, expand outward as a single-char center and as a between-chars center; track the global best span.

Solution approach

Reveal approach

Two competitive approaches. DP: build a 2D boolean table dp where dp[i][j] is true if s[i..j] is a palindrome. Base cases — every single character is a palindrome (dp[i][i] = true), every pair is one iff the two chars match. For lengths 3 and up, dp[i][j] = s[i] == s[j] AND dp[i+1][j-1]. Track the longest span as you fill. Expand-around-center: for each index 0..n-1, treat it both as an odd-length center (one char) and as the gap before it as an even-length center; expand left and right while characters match. Both run in O(n^2) time; expand-around-center is O(1) extra space. Manacher's algorithm solves it in O(n) but is rare in interviews.

Complexity

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

Related patterns

  • dynamic-programming
  • two-pointers
  • string-dp

Related problems

Asked at

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

  • Amazon
  • Microsoft
  • Adobe
  • Bloomberg

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →