Dynamic Programming: Longest repeating subsequence

Problem Statement:

You are given a string, you need to find the length of the longest repeating subsequence.

Example

Input: AABEBCDD
O/p: 3

Here the longest repeating subsequence is : ABD

Solution

What we will do is, we will get the LCS of the string itself with a condition being, if both the characters are same, they shouldn’t be on the same index in the two strings.

Example:

The LCS of the string 1 with string 1 will be string 1 only:

str1: AABEBCDD
str2: AABEBCDD

LCS: AABEBCDD.

But the o/p that we need is “ABD”. You can see that “E & C” are missing from the o/p because they repeat only once in the string.

So we need to select the characters, that are same but not in the same index.

So you can choose str1 index 0 “a” with str2 index 1 “a”. Similarly
you can choose str1 index 2 “b” with str2 index 4 “b” …

we will arrive at the solution

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;


int get_longest_repeating_subsequence(string str)
{
    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;
 
    //fill DP array bottom up approach
    for (int i=1; i<=n; i++)
    {
     
        for (int j=1; j<=n; j++)
        {
            // If characters match and indexes are not same
            if (str[i-1] == str[j-1] && i != j)
                dp[i][j] =  1 + dp[i-1][j-1];         
                      
            // If characters do not match
            else
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
    }
    return dp[n][n];
}

int main()
{   
    string str1 = "AABEBCDD";

    cout<<"The length is  = " <<get_longest_repeating_subsequence(str1)<<endl;
  
}

Output:

The length is = 3