|
In this article, we will learn how to find the Longest Palindromic Subsequence (LPS) of a sequence using C++ programming language. LPS is the longest subsequence of a given sequence that reads the same backward as forward.
Example:
Input:
Sequence: "BBABCBCAB"
Output:
Length of LPS is 7
Explanation: The LPS is "BABCBAB" of length 7.  LPS Example Approaches to Find LPS in C++ Language
In the recursive approach, we will generate all the possible subsequences and find the longest palindromic subsequence among them using recursion.
Approach:- Create a function lpsRecursive that takes a string str, and two indices i and j.
- Base Condition: If there is only one character (i == j), return 1.
- If there are only two characters and both are the same (str[i] == str[j]), return 2.
- If the characters at indices i and j match (str[i] == str[j]), include both characters in LPS and recur for the remaining substring.
- If the characters do not match, recursively find LPS by excluding one character at a time.
- Return the maximum length obtained by including or excluding the current character.
Below is the implementation of the above approach:
C++
// C++ program to find the length of the Longest Palindromic
// Subsequence (LPS) using recursion
#include <cstring>
#include <iostream>
using namespace std;
// Function to return the maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }
// Function to find the length of the Longest Palindromic
// Subsequence (LPS) using recursion
int lpsRecursive(const string& str, int i, int j)
{
// Base cases
if (i == j)
return 1;
if (str[i] == str[j] && i + 1 == j)
return 2;
// If characters match, include them in LPS and recur
// for remaining substring
if (str[i] == str[j])
return 2 + lpsRecursive(str, i + 1, j - 1);
// If characters do not match, recursively find LPS by
// excluding one character at a time
return max(lpsRecursive(str, i, j - 1),
lpsRecursive(str, i + 1, j));
}
int main()
{
string str = "BBABCBCAB";
cout << "Length of LPS is "
<< lpsRecursive(str, 0, str.length() - 1) << endl;
return 0;
}
Time Complexity: O(2^n)
Auxiliary Space: O(1)
We can use this optimization technique to store the results of expensive function calls and reuse them when the same inputs occur again.
Approach:- Create a 2D array dp of size n x n and initialize all values to -1.
- Implement a function lpsMemoization that takes str, i, j, and the memoization array dp.
- Base Condition: If there is only one character (i == j), return 1.
- If the result is already computed (dp[i][j] != -1), return it.
- If the characters at indices i and j match (str[i] == str[j]), store and return the result in the memoization array.
- Recursively compute and store results for the remaining substrings.
- Return the computed result from the memoization array.
Below is the implementation of the above approach:
C++
// C++ program to find the length of the Longest Palindromic
// Subsequence (LPS) using Memoization
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
// Function to return the maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }
// Function to find the length of the Longest Palindromic
// Subsequence (LPS) using Memoization
int lpsMemoization(const string& str, int i, int j,
vector<vector<int> >& dp)
{
// Base cases
if (i == j)
return 1;
if (str[i] == str[j] && i + 1 == j)
return 2;
// If the value is already computed, return it
if (dp[i][j] != -1)
return dp[i][j];
// If characters match, include them in LPS and
// recursively find LPS for the remaining substring
if (str[i] == str[j])
return dp[i][j]
= 2 + lpsMemoization(str, i + 1, j - 1, dp);
// If characters do not match, recursively find LPS by
// excluding one character at a time
return dp[i][j]
= max(lpsMemoization(str, i, j - 1, dp),
lpsMemoization(str, i + 1, j, dp));
}
int main()
{
string str = "BBABCBCAB";
int n = str.length();
// Initialize memoization table with -1
vector<vector<int> > dp(n, vector<int>(n, -1));
cout << "Length of LPS is "
<< lpsMemoization(str, 0, n - 1, dp) << endl;
return 0;
}
Time Complexity: O(n^2)
Auxiliary Space: O(n^2)
We can use the bottom-up approach by building the solution in a bottom-up manner using a table to store intermediate results.
Approach:- Create a 2D array dp of size n x n.
- Set the base conditions (dp[i][i] = 1).
- Iterate through the string, filling the table based on character matches.
- The value at dp[0][n-1] will be the length of the LPS.
Below is the implementation of the above approach:
C++
// C++ program to find the length of the Longest Palindromic
// Subsequence (LPS) using Bottom-Up (Tabulation)
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
// Function to return the maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }
// Function to find the length of the Longest Palindromic
// Subsequence (LPS) using Bottom-Up (Tabulation)
int lpsTabulation(const string& str)
{
int n = str.length();
vector<vector<int> > dp(n, vector<int>(n, 0));
// Base cases: Single characters are palindromic
// subsequences of length 1
for (int i = 0; i < n; i++)
dp[i][i] = 1;
// Build the dp table in bottom-up manner
for (int cl = 2; cl <= n; cl++) {
for (int i = 0; i < n - cl + 1; i++) {
int j = i + cl - 1;
if (str[i] == str[j] && cl == 2)
dp[i][j] = 2;
else if (str[i] == str[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
}
}
// dp[0][n-1] contains the length of LPS for str[0..n-1]
return dp[0][n - 1];
}
int main()
{
string str = "BBABCBCAB";
cout << "Length of LPS is " << lpsTabulation(str)
<< endl;
return 0;
}
Time Complexity: O(n^2)
Auxiliary Space: O(n^2)
We can also use a space-optimized approach that reduces the space complexity of the tabulated method by using only two rows instead of a matrix.
Approach:- Create a 2D array dp of size 2 x n.
- Set the base conditions (dp[0][j] = 0).
- Iterate through the string, filling the table based on character matches using only two rows.
- The value at dp[m % 2][n-1] will be the length of the LPS.
Below is the implementation of the above approach:
C++
// C++ program to find the length of the Longest Palindromic
// Subsequence (LPS) using Bottom-Up (Space-Optimization)
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
// Function to return the maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }
// Function to find the length of the Longest Palindromic
// Subsequence (LPS) using Bottom-Up (Space-Optimization)
int lpsSpaceOptimized(const string& str)
{
// Get the length of the input string
int n = str.length();
// Create a 2-row DP table to store results of
// subproblems
vector<vector<int> > dp(2, vector<int>(n, 0));
// Iterate over the string in reverse order
for (int i = n - 1; i >= 0; i--) {
// Each single character is a palindrome of length 1
dp[i % 2][i] = 1;
for (int j = i + 1; j < n; j++) {
// If characters match, add 2 to the result of
// the remaining substring
if (str[i] == str[j])
dp[i % 2][j] = dp[(i + 1) % 2][j - 1] + 2;
else
// If characters don't match, take the
// maximum of excluding either character
dp[i % 2][j] = max(dp[(i + 1) % 2][j],
dp[i % 2][j - 1]);
}
}
// The result for the entire string is stored in dp[0][n
// - 1]
return dp[0][n - 1];
}
int main()
{
// Input string
string str = "BBABCBCAB";
// Output the length of the longest palindromic
// subsequence
cout << "Length of LPS is " << lpsSpaceOptimized(str)
<< endl;
return 0;
}
Time Complexity: O(n^2)
Auxiliary Space: O(n)
|
Clearing Bits in C++
KD Trees in C++
C++ Implementation Double-Ended Queue
Implementation of Rabin Karp Algorithm in C++
Segment Tree in C++