Find Longest Palindromic Subsequence II
Given a string s, return the length of the longest good palindromic subsequence in s such that:
- It has an even length.
- No two consecutive characters are equal, except the two middle ones.
Example:
Input: s = “bbabab”
Output: 4
Explanation: The longest good palindromic subsequence of s is “baab”.Input: s = “dcbccacdb”
Output: 4
Explanation: The longest good palindromic subsequence of s is “dccd”
Approach:
Uses a dynamic programming approach. We’ll use 2D vector of pairs dp[i][j] to store the length of the longest good palindromic subsequence and the last character of the subsequence for each substring s[i, j] of the given string.
Iterate over each substring of the given string in reverse order. For each substring, compare the characters at the left and right ends.
Case 1: Characters at Ends are Equal: If the characters at the left and right ends of the substring are the same and are not the same as the last character of the longest good palindromic subsequence of the substring excluding the left and right ends, then extend the subsequence by adding the characters at the left and right ends. This is because adding the characters at the ends will form a longer good palindromic subsequence.
Case 2: Characters at ends are Not Equal or Same as Last Character of Subsequence: If the characters at the ends are not equal or are the same as the last character of the subsequence, then the longest good palindromic subsequence of the current substring is the longer one between the subsequences of the substrings excluding the left end and excluding the right end. This is because adding either character at the ends will not form a good palindromic subsequence.
After iterating over all substrings, return the length of the longest good palindromic subsequence of the given string, which is stored in dp[0][n – 1].first
Step-by-step approach:
- Create 2D vector, dp, to store the length of the longest good palindromic subsequence and the last character of the subsequence for each substring of s.
- Iterate over each substring of s in reverse order.
- For each substring, compare characters at the left and right ends:
- If they are the same and not the same as the last character of the longest good palindromic subsequence of the substring excluding the left and right ends, extend the subsequence by adding these characters.
- If the length of the longest good palindromic subsequence of the substring excluding the right end is greater than or equal to that of the substring excluding the left end, choose the subsequence of the substring excluding the right end.
- Otherwise, choose the subsequence of the substring excluding the left end.
- For each substring, compare characters at the left and right ends:
- Return the length of the longest good palindromic subsequence of s
Below is the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
int longestGoodPalindromeSubsequence(string s)
{
int n = s.length();
// Initialize a 2D vector to store the length of the
// longest good palindromic subsequence and the last
// character of the subsequence for each substring of s
vector<vector<pair<int, char> > > dp(
n, vector<pair<int, char> >(n));
// Iterate over each substring of s in reverse order
for (int l = n - 1; l >= 0; l--) {
for (int r = l + 1; r < n; r++) {
// If the characters at the l and r ends of the
// substring are the same and are not the same
// as the last character of the longest good
// palindromic subsequence of the substring
// excluding the l and r ends, then we can
// extend the subsequence by adding the
// characters at the l and r ends
if (s[l] == s[r]
&& s[l] != dp[l + 1][r - 1].second) {
dp[l][r]
= { 2 + dp[l + 1][r - 1].first, s[l] };
}
// If the length of the longest good palindromic
// subsequence of the substring excluding the r
// end is greater than or equal to that of the
// substring excluding the l end, then we choose
// the subsequence of the substring excluding
// the r end
else if (dp[l][r - 1].first
>= dp[l + 1][r].first) {
dp[l][r] = dp[l][r - 1];
}
// Otherwise, we choose the subsequence of the
// substring excluding the l end
else {
dp[l][r] = dp[l + 1][r];
}
}
}
// Return the length of the longest good palindromic
// subsequence of s
return dp[0][n - 1].first;
}
int main()
{
// Define a static input string
string s = "abcabcabb";
// Call the longestGoodPalindromeSubsequence method with
// the static input
int length = longestGoodPalindromeSubsequence(s);
// Print the length of the longest good palindromic
// subsequence
cout << "The length of the longest good palindromic "
"subsequence in \""
<< s << "\" is " << length << "." << endl;
return 0;
}
import java.util.*;
public class Main {
static int longestGoodPalindromeSubsequence(String s) {
int n = s.length();
// Initialize a 2D array to store the length of the
// longest good palindromic subsequence and the last
// character of the subsequence for each substring of s
Pair[][] dp = new Pair[n][n];
// Initialize the dp array with default values
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = new Pair(0, ' ');
}
}
// Iterate over each substring of s in reverse order
for (int l = n - 1; l >= 0; l--) {
for (int r = l + 1; r < n; r++) {
// If the characters at the l and r ends of the
// substring are the same and are not the same
// as the last character of the longest good
// palindromic subsequence of the substring
// excluding the l and r ends, then we can
// extend the subsequence by adding the
// characters at the l and r ends
if (s.charAt(l) == s.charAt(r)
&& s.charAt(l) != dp[l + 1][r - 1].second) {
dp[l][r] = new Pair(2 + dp[l + 1][r - 1].first, s.charAt(l));
}
// If the length of the longest good palindromic
// subsequence of the substring excluding the r
// end is greater than or equal to that of the
// substring excluding the l end, then we choose
// the subsequence of the substring excluding
// the r end
else if (dp[l][r - 1].first >= dp[l + 1][r].first) {
dp[l][r] = dp[l][r - 1];
}
// Otherwise, we choose the subsequence of the
// substring excluding the l end
else {
dp[l][r] = dp[l + 1][r];
}
}
}
// Return the length of the longest good palindromic
// subsequence of s
return dp[0][n - 1].first;
}
public static void main(String[] args) {
// Define a static input string
String s = "abcabcabb";
// Call the longestGoodPalindromeSubsequence method with
// the static input
int length = longestGoodPalindromeSubsequence(s);
// Print the length of the longest good palindromic
// subsequence
System.out.println("The length of the longest good palindromic "
+ "subsequence in \"" + s + "\" is " + length + ".");
}
// Define a Pair class to store the length and last character of a subsequence
static class Pair {
int first;
char second;
Pair(int first, char second) {
this.first = first;
this.second = second;
}
}
}
// This code is contributed by Shivam Gupta
function longestGoodPalindromeSubsequence(s) {
const n = s.length;
// Initialize a 2D array to store the length of the
// longest good palindromic subsequence and the last
// character of the subsequence for each substring of s
const dp = new Array(n).fill(null).map(() => new Array(n).fill(null));
// Iterate over each substring of s in reverse order
for (let l = n - 1; l >= 0; l--) {
for (let r = l + 1; r < n; r++) {
// If the characters at the l and r ends of the
// substring are the same and are not the same
// as the last character of the longest good
// palindromic subsequence of the substring
// excluding the l and r ends, then we can
// extend the subsequence by adding the
// characters at the l and r ends
if (s[l] === s[r] && s[l] !== (dp[l + 1][r - 1] ?
dp[l + 1][r - 1].second : null)) {
dp[l][r] = { first: 2 + (dp[l + 1][r - 1] ?
dp[l + 1][r - 1].first : 0), second: s[l] };
}
// If the length of the longest good palindromic
// subsequence of the substring excluding the r
// end is greater than or equal to that of the
// substring excluding the l end, then we choose
// the subsequence of the substring excluding
// the r end
else if (dp[l][r - 1] && dp[l][r - 1].first >= (dp[l + 1][r] ?
dp[l + 1][r].first : 0)) {
dp[l][r] = dp[l][r - 1];
}
// Otherwise, we choose the subsequence of the
// substring excluding the l end
else {
dp[l][r] = dp[l + 1][r];
}
}
}
// Return the length of the longest good palindromic
// subsequence of s
return dp[0][n - 1].first;
}
// Define a static input string
const s = "abcabcabb";
// Call the longestGoodPalindromeSubsequence method with
// the static input
const length = longestGoodPalindromeSubsequence(s);
// Print the length of the longest good palindromic
// subsequence
console.log(`The length of the longest good palindromic
subsequence in "${s}" is ${length}.`);
// This code is contributed by Rambabu
Output
The length of the longest good palindromic subsequence in "abcabcabb" is 4.
Time Complexity: O(n^2)
Auxiliary Space: O(n^2)