Longest Palindromic Substring - Solution & Explanation
Problem Statement
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd" Output: "bb"
Constraints:
1 <= s.length <= 1000sconsist of only digits and English letters.
Approach Overview
Problem Overview: Given a string s, return the longest substring that reads the same forward and backward. The substring must be contiguous, so you cannot rearrange characters or skip indices.
This problem sits at the intersection of string manipulation and palindrome detection. The challenge is checking all possible centers efficiently without recomputing the same substrings repeatedly.
Approach 1: Expand Around Center (Time: O(n2), Space: O(1))
A palindrome mirrors around its center. Every palindrome can have either one center (odd length like aba) or two centers (even length like abba). Iterate through the string and treat each index as a potential center. Expand outward using two pointers while the characters match.
For each index i, run two expansions: one with (i, i) for odd-length palindromes and another with (i, i+1) for even-length palindromes. Track the longest substring found during these expansions. Each expansion moves the two pointers outward until the characters differ or boundaries are reached.
This approach avoids storing intermediate states and checks only meaningful palindrome candidates. In the worst case (e.g., aaaaa) each expansion scans many characters, leading to O(n2) time, but the constant factors are small and memory usage stays O(1).
Approach 2: Dynamic Programming (Time: O(n2), Space: O(n2))
The dynamic programming approach builds a table dp[i][j] indicating whether substring s[i..j] is a palindrome. Single characters are palindromes, and pairs of equal characters form length-2 palindromes. For longer substrings, a substring is a palindrome if s[i] == s[j] and dp[i+1][j-1] is true.
Fill the DP table by increasing substring length. Each time a palindrome is confirmed, update the longest substring indices. This method ensures every substring is evaluated exactly once.
The main advantage is clarity: the palindrome property is expressed directly through subproblems. The downside is memory usage, since the DP table requires O(n2) space. For long strings this becomes expensive compared to the center-expansion approach.
Recommended for interviews: Expand Around Center is the solution most interviewers expect. It demonstrates understanding of palindrome symmetry and avoids unnecessary memory. Dynamic Programming shows strong problem decomposition but is rarely preferred due to its O(n2) space cost. Mentioning Manacher’s algorithm (O(n) time) can earn bonus points, though implementing it correctly during interviews is uncommon.
Approach 1: Expand Around Center
This approach is based on the observation that a palindrome mirrors around its center. Therefore, if we choose a center, we can expand outward to check for the longest possible palindrome. We can have centers between each two characters as well as on each character to cater for even and odd length palindromes.
The solution iterates over each character, considering it as a possible center of a palindrome. It tries to expand around it for both odd and even lengths. We maintain the longest found palindrome's start and end indices, which are used to construct the result substring in the end.
Complexity
Time Complexity: O(n^2) because we potentially expand around n centers.
Space Complexity: O(1), aside from the space required for the output string.
Approach 2: Dynamic Programming
In this approach, a 2D DP table is constructed where dp[i][j] is true if the string s[i...j] is a palindrome. Each entry is dependent on smaller substring checks. This method leverages overlapping subproblems.
We make use of a DP table that captures the palindrome status for each (i,j) substring. The status gets updated from prior adjacent matches. Substring boundaries clarify palindromes, storing the starting position and length of the longest identified palindrome.
Code
C
C++
Java
Python
C#
JavaScript
Go
TypeScript
Rust
Nim
Complexity
Time Complexity: O(n^2) due to the complete 2D table scan.
Space Complexity: O(n^2) as the DP table fully holds substring truths.
Approach 3: Enumerate Palindrome Midpoint
We can enumerate the midpoint of the palindrome, spread to both sides, and find the longest palindrome.
The time complexity is O(n^2), and the space complexity is O(1). Here, n is the length of the string s.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Expand Around Center | Time Complexity: Space Complexity: |
| Dynamic Programming | Time Complexity: |
| Enumerate Palindrome Midpoint | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Expand Around Center | O(n^2) | O(1) | Best general solution. Minimal memory and easy to implement in interviews. |
| Dynamic Programming | O(n^2) | O(n^2) | Useful when learning DP patterns or when substring states must be reused. |
| Manacher's Algorithm | O(n) | O(n) | Optimal theoretical solution. Rarely required in interviews due to implementation complexity. |
Video Solution
Longest Palindromic Substring - Python - Leetcode 5 • NeetCode • 809,465 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Palindromic Substring easy or hard?
How to solve Longest Palindromic Substring in O(n)?
Longest Palindromic Substring Python or Java solution?
What is the best approach for Longest Palindromic Substring?
Is Longest Palindromic Substring asked at Google/Amazon/Meta?
What data structure is used in Longest Palindromic Substring?
What is the time complexity of Longest Palindromic Substring?
Ready to solve this problem?
Practice Longest Palindromic Substring with our built-in code editor and test cases.
Practice on FleetCode