This is a standard Dynamic Programming problem. In this post, we’ll try to derive the bottom-up DP approach by first considering a top-down recursive approach.
Approach 1: Recursion with memoization
Consider a string “bbacab”. To find the longest palindromic substring, we’ll consider two characters simultaneously from both ends of the string and try to go in further. Let’s start by considering two pointers, one pointing to the first index and the other pointing to the last index.
String (s): b b a c a b
0 1 2 3 4 5
Pointer 1 (ptr1): index 0 (b) & pointer 2 (ptr2): index 5 (b)
s[ptr1] == s[ptr2]. Since these characters lie at both ends of the string, we are sure that these should be in the answer. Now all we have to do is find longest palindromic subsequence b/w index 1..4. Answer = 2 + length(1..4)
ptr1 = 1, ptr2 = 4. Now, s[ptr1]!=s[ptr2]. So index 1 and 4 together do not form a palindrome. So we should find the longest palindromic subsequence b/w index 1..3 and also 2..4. Ans for this subproblem = max(length(1..3), length(2..4))
Clearly, length of longest palindromic subsequence b/w 1..3 is 1 (as all characters are distinct, consider any one character "b" or "a" or "c" to be a palindrome). Length of longest palindromic subsequence b/w index 2..4 is 3 ("aca" is a palindrome).
So final answer becomes "bacab" with length 5.
// top-down -> recursion + memo
// states -> start, end
int longestPalindromeSubseq(string s) {
vector<vector<int>> memo(s.length(), vector<int>(s.length(), -1));
return helper(s, 0, s.length()-1, memo);
}
int helper (string& s, int start, int end, vector<vector<int>>& memo) {
if (start == end)
return 1;
if (start>end)
return 0;
if (memo[start][end]!=-1)
return memo[start][end];
if (s[start] == s[end]) {
memo[start][end] = 2+helper(s, start+1, end-1, memo);
} else {
memo[start][end] = max(helper(s, start+1, end, memo), helper(s, start, end-1, memo));
}
return memo[start][end];
}
Time complexity: O(n^2)
Approach 2: Dynamic Programming
It is easy to identify that each state in recursion is defined by the start index and end index. Define a 2D DP array dp[i][j] = length of longest palindromic subsequence from index i to j. If i>j, it is an invalid sequence so dp[i][j]=0. When i=j, the sequence consists of only one character so it is a valid palindrome of length 1, dp[i][j] = 1. Now, as you can see in the above solution, when s[i]==s[j], dp[i][j] = 2+dp[i+1][j-1] otherwise dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
// bottom up solution using DP
// state variables -> start index, end index
// dp[i][j] = length of longest palindromic subsequence from index i to j
int longestPalindromeSubseq(string s) {
int size = s.length();
// sanity check
if (size==0)
return 0;
int dp[size][size];
fill(&dp[0][0], &dp[0][0]+size*size, 0);
for (int i=0; i<size; i++)
dp[i][i]=1;
int col=0;
while (col<size) {
for (int j=col+1, i=0; j<size; j++, i++)
if (s[i]==s[j])
dp[i][j]=2+dp[i+1][j-1];
else
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
col++;
}
return dp[0][size-1];
}
Time complexity: O(n^2)