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 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 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

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →