Longest Palindromic Substring
LeetCode #5 · Medium · Dynamic Programming · C++ solution with worked-out approach and complexity analysis.
Approach
Dynamic Programming
dp[j][i] = true if substring s[j..i] is a palindrome. Base case: single chars are palindromes. Transition: s[j..i] is palindrome if s[j]==s[i] and (length<=3 or s[j+1..i-1] is palindrome).
Time
O(n^2)
fill the DP table
Space
O(n^2)
2D DP table
Problem description(from LeetCode)
Given a string s, return the longest palindromic substring in s.
Examples
Example 1
- Input:
- s = "babad"
- Output:
- "bab"
- Note:
- "aba" is also a valid answer.
Example 2
- Input:
- s = "cbbd"
- Output:
- "bb"
Constraints
- •1 <= s.length <= 1000
- •s consist of only digits and English letters
C++ Solution
solution.cpp
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() <= 1) return s;
int n = s.size();
int start = 0, maxLength = 1;
vector<vector<bool>> dp(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) {
dp[i][i] = true;
for (int j = 0; j < i; j++) {
int length = i - j + 1;
if (s[i] == s[j] && (length <= 3 || dp[j + 1][i - 1])) {
dp[j][i] = true;
if (length > maxLength) {
maxLength = length;
start = j;
}
}
}
}
return s.substr(start, maxLength);
}
};