Skip to content
AI360Xpert
Beta
Back to 1-D Dynamic Programming
Difficulty: Medium1-D Dynamic Programming

Longest Palindromic Substring

Problem in Plain English

Given a string s, return any longest contiguous block that reads the same forwards and backwards.

Problem Statement

You are given a string s. A palindrome reads identically forwards and backwards.

Return any longest palindromic contiguous substring of s. Single characters always qualify, so the answer is never empty.

Constraints

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

Examples

Example 1

Input
s = "babad"
Output
"bab"

Indices 0..2 form bab: its outer letters match and its middle is a. No length-4 or length-5 substring is a palindrome. The tied answer aba at 1..3 is also valid; the snippets retain the first longest answer.

Example 2

Input
s = "cbbd"
Output
"bb"

The gap between indices 1 and 2 is the center of bb. Its next outer pair is c and d, which fails, so the length is 2. Looking only at character centers would miss this answer.

Example 3

Input
s = "a"
Output
"a"

The only non-empty substring is the one character itself. It is already a palindrome, and neither expansion can move beyond the string.

Example 4

Input
s = "aaaa"
Output
"aaaa"

Every outer pair matches, including the pair around the middle gap. The entire string is the longest palindrome; this input also forces many repeated comparisons in brute force.

Intuition

A palindrome matches pairs at equal distances from its middle. In Example 1, the middle a at index 1 grows into bab; the middle b at index 2 grows into aba. Both have length 3, and either is valid. A middle may be a character or a gap, as bb in cbbd shows. Expanding each middle avoids checking every substring, but still repeats comparisons in overlapping palindromes. Manacher's algorithm reuses known lengths at mirrored centers to remove that repetition. It stores one radius per center, trading linear memory for linear time. We seek a contiguous substring, so skipping characters is not allowed.

Approaches

Check Every Substring

Solution Details

Reveal Check Every Substring: intuition, complexity, and code

Hints

Hint 1
Any palindrome is fixed by its middle, so enumerate middles instead of slicing every start and end.
Hint 2
Each position seeds two growths: odd around the character and even around the gap after it.
Hint 3
Walk both pointers outward while the letters match and keep the widest window seen.
Hint 4
To avoid repeating comparisons, keep the palindrome reaching farthest right. Its symmetric centers already have reusable radii.
Hint 5
Insert separators to unify odd and even centers; initialize radius at i from min(radius[2 * center - i], right - i) only when i is inside right, then expand.

Edge Cases

  • A single character returns itself with no growth possible.
  • Uniform strings like "aaaa" expand the full width from an early middle.
  • Strings with no repeat, like "abcd", keep the length-1 seed from the first middle.
  • Case-sensitive matching matters: Aa has longest length 1, whereas aa has length 2. Digits use the same character comparison.
  • Tied longest answers such as bab and aba are both valid; a strict improvement test deterministically keeps the earlier one.

Common Mistakes and Interview Tips

  • Checking only odd middles misses even answers like "bb" in "cbbd".
  • Comparing lengths with stale bounds, or slicing with an off-by-one end, returns a shifted window.
  • Continuing the outward walk past the first mismatch fabricates mirrors instead of stopping the growth.
  • Slicing a growing Python answer on every successful expansion allocates repeated copies. Keep indices and slice once to retain constant auxiliary space.
  • Confusing a substring with a subsequence permits skipped characters and solves a different problem.
  • Using an unclipped mirror radius can claim matches beyond the known boundary. At transformed i = 7 in Example 1, the mirror radius is 3 but the initial safe radius is 1.
  • Treating a transformed radius as a half-length in the original string gives the wrong answer. With the inserted separators, radius equals original length and start is floor((i - radius)/2).
  • Using >= to replace the best palindrome changes the documented earliest-tie behavior, though another longest answer is allowed by the problem.
  • Choosing a separator that can occur in the input breaks the transformed representation. # is absent from the stated English-letter and digit alphabet.

Key Takeaway

Every palindrome has a center. Expanding all centers removes cubic substring checking with constant auxiliary space; Manacher then reuses mirrored radii inside the farthest-reaching palindrome to achieve linear time with linear storage. Reuse only the overlap whose matches are already proven, and expand beyond its boundary.