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.The Longest Palindromic Substring problem asks you to find the longest contiguous substring in a string that reads the same forward and backward. A common and efficient strategy is the expand around center technique. Every palindrome has a center (either a single character or a gap between two characters). By expanding outward from each possible center and checking matching characters, you can track the longest valid palindrome. This approach runs in O(n^2) time and requires O(1) extra space.
Another approach uses Dynamic Programming. Here, a 2D table stores whether a substring s[i..j] is a palindrome. You build the solution from smaller substrings to larger ones, marking entries based on previously computed results. While this also takes O(n^2) time, it uses O(n^2) space. Interviewers often prefer the center expansion approach due to its simplicity and lower memory usage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Expand Around Center | O(n^2) | O(1) |
| Dynamic Programming | O(n^2) | O(n^2) |
| Brute Force | O(n^3) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
How can we reuse a previously computed palindrome to compute a larger palindrome?
If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?
Complexity based hint:</br> If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.
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.
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.
1#include <stdio.h>
2#include <string.h>
3
4int expandAroundCenter(char *s, int left, int right) {
5
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.
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.
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.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Longest Palindromic Substring is a well-known interview problem frequently discussed in FAANG-style interviews. It tests understanding of strings, two pointers, and dynamic programming concepts. Candidates are often expected to explain multiple approaches and their trade-offs.
The most commonly recommended approach is the expand-around-center technique. It checks palindromes by expanding from each character and pair of characters as potential centers. This achieves O(n^2) time with O(1) extra space, making it efficient and interview-friendly.
Expand-around-center is often preferred because it uses constant extra space and is simpler to implement. Dynamic programming requires maintaining a 2D table, which increases memory usage. In interviews, the center expansion approach demonstrates both efficiency and clean logic.
The problem mainly relies on string traversal rather than complex data structures. For the dynamic programming solution, a 2D array or matrix is used to store whether substrings are palindromes. The center expansion method only requires a few variables, making it very space efficient.
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.