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 <= 1000s consist of only digits and English letters.Problem Overview: Given a string s, return the longest substring that reads the same forward and backward. The substring must be continuous. You need to scan the string and detect the largest window where characters mirror around a center.
Approach 1: Expand Around Center (O(n^2) time, O(1) space)
A palindrome mirrors around its center. For each index in the string, treat it as the center of a palindrome and expand outward using two pointers. Handle both odd-length palindromes (center = i) and even-length palindromes (center = i, i+1). While the characters at the left and right pointers match, expand further and update the best substring length.
This method iterates through the string once and performs expansion at each position. In the worst case (like "aaaaa"), every expansion scans many characters, leading to O(n^2) time. The advantage is constant extra memory since only indices are tracked. This approach relies heavily on Two Pointers applied to a String. Most production implementations and interview solutions use this technique because it is simple and memory efficient.
Approach 2: Dynamic Programming (O(n^2) time, O(n^2) space)
Dynamic programming stores whether each substring is a palindrome. Create a 2D table dp[i][j] that represents whether substring s[i..j] is palindromic. A substring is a palindrome if the characters match (s[i] == s[j]) and the inner substring s[i+1..j-1] is also a palindrome.
Initialize base cases for length 1 and length 2 substrings. Then iterate over substring lengths from 3 to n. Whenever dp[i][j] becomes true, update the longest range. The table ensures each substring state is computed once, giving O(n^2) time. However, the memory footprint is also O(n^2), which can be significant for long strings. This approach demonstrates classic Dynamic Programming where overlapping subproblems are reused.
Recommended for interviews: Expand Around Center is the expected solution in most coding interviews. It achieves optimal practical performance with O(1) extra space and straightforward logic. Dynamic Programming proves you understand palindrome substructure but uses unnecessary memory. A strong candidate usually explains the brute-force idea, then moves quickly to the center-expansion technique.
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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 | Complexity |
|---|---|
| Expand Around Center | Time Complexity: Space Complexity: |
| Dynamic Programming | Time Complexity: |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Expand Around Center | O(n^2) | O(1) | Best general solution. Minimal memory and simple logic for interview settings. |
| Dynamic Programming | O(n^2) | O(n^2) | Useful when demonstrating DP state transitions or learning palindrome subproblems. |
Longest Palindromic Substring - Python - Leetcode 5 • NeetCode • 629,073 views views
Watch 9 more video solutions →Practice Longest Palindromic Substring with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor