Longest Repeated Subsequence.cpp

/*Given a string, print the longest repeating subsequence such that the two subsequence don’t have same string character at same position, i.e., any i’th character in the two subsequences shouldn’t have the same index in the original string.*/


#include <bits/stdc++.h> 
using namespace std; 
  
// This function mainly returns LCS(str, str) 
// with a condition that same characters at 
// same index are not considered. 
string longestRepeatedSubSeq(string str) 
{ 
    // THIS PART OF CODE IS SAME AS BELOW POST.  
    // IT FILLS dp[][] 
    // https://www.geeksforgeeks.org/longest-repeating-subsequence/ 
    // OR the code mentioned above. 
    int n = str.length(); 
    int dp[n+1][n+1]; 
    for (int i=0; i<=n; i++) 
        for (int j=0; j<=n; j++) 
            dp[i][j] = 0; 
    for (int i=1; i<=n; i++) 
        for (int j=1; j<=n; j++) 
            if (str[i-1] == str[j-1] && i != j) 
                dp[i][j] =  1 + dp[i-1][j-1]; 
            else
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]); 
  
  
    // THIS PART OF CODE FINDS THE RESULT STRING USING DP[][] 
    // Initialize result 
    string res = ""; 
  
    // Traverse dp[][] from bottom right 
    int i = n, j = n; 
    while (i > 0 && j > 0) 
    { 
        // If this cell is same as diagonally 
        // adjacent cell just above it, then  
        // same characters are present at  
        // str[i-1] and str[j-1]. Append any  
        // of them to result. 
        if (dp[i][j] == dp[i-1][j-1] + 1) 
        { 
           res = res + str[i-1]; 
           i--; 
           j--; 
        } 
  
        // Otherwise we move to the side 
        // that that gave us maximum result 
        else if (dp[i][j] == dp[i-1][j]) 
            i--; 
        else
            j--; 
    } 
  
    // Since we traverse dp[][] from bottom, 
    // we get result in reverse order. 
    reverse(res.begin(), res.end()); 
  
    return res; 
} 
  
// Driver Program 
int main() 
{ 
    string str = "AABEBCDD"; 
    cout << longestRepeatedSubSeq(str); 
    return 0; 
} 
//contributed by saurabh negi