Coding Interview PatternsLongest Palindromic Substring
MediumDynamic Programming
Longest Palindromic Substring
Explanation & Solution
Description
Given a string s, return the longest palindromic substring in s.
A palindrome is a string that reads the same forward and backward.
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer since it has the same length.
Constraints
1 <= s.length <= 1000sconsists of only lowercase English letters.
Approach
Dynamic Programming pattern
1. Handle Base Case
- If the string has length 0 or 1, return it directly since it is already a palindrome.
2. Initialize Tracking Variables
- Set
start = 0andmaxLen = 1to track the starting index and length of the longest palindromic substring found so far.
3. Expand Around Center
- Define a helper function
expandAroundCenter(left, right)that expands outward as long as the characters atleftandrightmatch. - Each time a longer palindrome is found, update
startandmaxLen.
4. Iterate Through Each Center
- For each index
i, callexpandAroundCenter(i, i)for odd-length palindromes (single character center). - Also call
expandAroundCenter(i, i + 1)for even-length palindromes (two character center). - This covers all possible palindromic substrings.
5. Return the Result
- Extract and return the substring from
starttostart + maxLen.
Key Insight
- The expand around center technique avoids the need for a full 2D DP table. Every palindrome has a center (a single character for odd-length or a pair for even-length), and we can efficiently check all possible centers in linear passes.
Time
O(n^2)for each of the n centers, expansion takes up to O(n) time.Space
O(1)only a few variables are used.Visualization
Input:
[b, a, b, a, d]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps