Strings: Longest Repeating Subsequence

Problem Statement:

Given a string find the length of the longest repeating sub sequence.
Here we need to find the sub sequence, not sub string. Hence sub sequence need not require to occupy consecutive positions.

You need to find that sub sequence, such that the two sub sequence don’t have same string character at same position.

Example

Input: abacbc
Output: 2

Here we can have 2 sub sequence as shown below:

“a” from index 0, “b” from index 1, “c” from index 3.
“a” from index 2, “b” from index 4, “c” from index 5.

It is also satisfying the condition that no sub sequence share the same index.

But below sequence is not considered as sub sequence, because they share “a” from index 0.

“a” from index 0, “b” from index 1, “c” from index 3.
“a” from index 0, “b” from index 4, “c” from index 5.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <queue>

using namespace std;


int longest_repeating_sub_string(string str)
{
    int n = str.length();
 
    // create DP array
    int dp[n+1][n+1];

    //initialize DP array
    for (int i=0; i<=n; i++)
        for (int j=0; j<=n; j++)
            dp[i][j] = 0;
 
    // fill DP array
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            // char are same, but index are not same
            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]);
        }
    }
    return dp[n][n];
}
 
// Driver Program
int main()
{
    string str = "aabb";
    cout << "The length of LCR is " << longest_repeating_sub_string(str)<<endl;
    return 0;
}

Output:

The length of LCR is 2