Problem Statement

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.

Examples:

Input: str = "aabb"
Output: "ab"

Input: str = "aab"
Output: "a"
The two subsequence are 'a'(first) and 'a'
(second). Note that 'b' cannot be considered
as part of subsequence as it would be at same
index in both.

Problem Link

Longest Repeated Subsequence - GeeksforGeeks

Code

class Solution {
public:
    int longestCommonSubsequence(string text1) {
        int m = text1.size();
       
        
        vector<vector<int>> dp(m+1,vector<int>(m+1));
        
        for(int i=0;i<=m;i++)
        {
            for(int j=0;j<=m;j++)
            {
                if(!i||!j)
                    dp[i][j] = 0;
                
                else if(text1[i-1]==text1[j-1] **and i!=j**)
                    dp[i][j] = 1 + dp[i-1][j-1];
                
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                    
            }
        }
        return dp[m][m];
    }
};

Complexity Analysis

Time and Space Complexity of the above implementation is O(m*m)