Longest Palindromic Substring
Problem Statement
Given a string s, return the longest palindromic substring in s. If there are multiple answers with the same maximum length, returning any one of them is acceptable.
Input
A string s.
Output
A string: any longest contiguous substring of s that is a palindrome.
Constraints
- •
1 <= s.length <= 1000 - •
s consists of digits and English letters.
Examples
Example 1
s = babad
babExample 2
s = cbbd
bbExample 3
s = a
aLearning Objectives
- Reuse interval palindrome states to identify valid substrings.
- Track the best start and length while filling the DP table.
- Handle both odd-length and even-length palindromes.
- Compare interval DP with center expansion for the same problem.
Intuition
This is the optimisation version of counting palindromic substrings. The validity question is the same: do the endpoints match, and is the inside already a palindrome? The difference is that we do not count every true interval; we keep the longest true interval seen so far.
Filling by increasing length is important. When considering s[i..j], the state for s[i + 1..j - 1] must already be known. Each time an interval is true and longer than the current best, update the saved start and length. At the end, slice that range from the original string.
Common mistakes
- ×Solving longest palindromic subsequence instead; this problem requires a contiguous substring.
- ×Checking endpoints without verifying that the inside substring is also a palindrome.
- ×Ignoring even-length palindromes such as **bb**.
- ×Updating the best range before confirming the interval is valid.
- ×Returning only the length when the problem asks for the substring.
State Definition
Let dp[i][j] be true when substring s[i..j] is a palindrome. Alongside the table, maintain bestStart and bestLength for the longest true interval found so far.
State Transition
Process lengths from 1 to n. For each interval i..j, set dp[i][j] to true if s[i] == s[j] and either length <= 2 or dp[i + 1][j - 1] is true.
Base behavior is built into the length rule: length 1 substrings are palindromes, and length 2 substrings are palindromes only when their two characters match. Whenever dp[i][j] becomes true and length > bestLength, update the best range to i..j. The final answer is s.substring(bestStart, bestStart + bestLength).
Solutions
Solution 1: Interval DP tracking the best range
Use a boolean palindrome table just like Palindromic Substrings, but instead of counting all true states, remember the longest true interval.
Step-by-step
- Initialise bestStart = 0 and bestLength = 1 because every non-empty string has a one-character palindrome.
- Iterate substring lengths from 1 to n.
- Mark dp[start][end] true when endpoints match and the inside is valid.
- If the valid interval is longer than the saved best, update bestStart and bestLength.
- Return the substring represented by the best range.
O(n^2)
O(n^2)
Every substring interval is checked once, and the table stores O(n^2) booleans.
Java implementation
Solution 2: Expand around every center
Use this when the interviewer wants the simplest O(1)-space implementation. It is usually preferred in production unless another part of the solution needs the full palindrome table.
Every palindrome expands from a center. Try each character as an odd center and each gap as an even center, then keep the longest expansion seen.
Step-by-step
- Start with the first character as the best palindrome.
- For each center index, compute the longest odd palindrome and the longest even palindrome around that center.
- Convert the winning length back to start and end indices.
- Update the saved range only when the new palindrome is longer.
- Return the substring covered by the saved range.
O(n^2)
O(1)
There are O(n) centers, and each expansion can scan O(n) characters in the worst case.
Java implementation
Dry Run
Sample input
s = babad. The interval DP is filled by increasing length while tracking the first longest palindrome found.
| length | ranges that become true | best after length | reason |
|---|---|---|---|
| 1 | b, a, b, a, d | b | Single characters initialise valid palindromes. |
| 2 | none | b | No adjacent equal pair exists. |
| 3 | bab at 0..2; aba at 1..3 | bab | Both ranges have matching endpoints and true one-character interiors; the first length-3 range remains best. |
| 4 | none | bab | Every length-4 candidate fails an endpoint or inside check. |
| 5 | none | bab | The full string has different endpoints, so it is not a palindrome. |
The saved range is bab, so the method returns bab. A tie policy that updates on equal length could return aba, which is also valid.
Complexity Analysis
Both authored approaches are O(n^2) time. Interval DP spends O(n^2) space to reuse states; center expansion keeps only the best range and is the usual space-optimised answer.
Interval DP tracking the best range
O(n^2)
O(n^2)
Every substring interval is checked once, and the table stores O(n^2) booleans.
Expand around every center
O(n^2)
O(1)
There are O(n) centers, and each expansion can scan O(n) characters in the worst case.
Interview Tips
Start by distinguishing substring from subsequence. Then give the interval recurrence and mention that increasing length guarantees the inner state is ready. If you choose center expansion in code, still explain both odd and even centers; missing even centers is the classic bug.
Likely follow-ups
- How would you return the number of palindromic substrings instead of the longest one?
- How would you return all longest palindromic substrings if there are ties?
- Can you solve this in linear time with Manacher's algorithm, and why is it rarely expected in interviews?
- How would the answer change if you were allowed to delete characters, making it a subsequence problem?
Similar Problems
Key Takeaways
- Longest Palindromic Substring is interval DP plus best-range tracking.
- A valid longer palindrome needs matching endpoints and a valid inner substring.
- Even-length palindromes must be handled explicitly.
- Center expansion gives the same O(n^2) time with O(1) extra space.