Longest Repeating Subsequence - GeeksforGeeks

Longest Repeating Subsequence - GeeksforGeeks
Given a string, find length of the longest repeating subseequence 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.

This problem is just the modification of Longest Common Subsequence problem. The idea is to find the LCS(str, str) where str is the input string with the restriction that when both the characters are same, they shouldn’t be on the same index in the two strings.

int findLongestRepeatingSubSeq(string str)

{

    int n = str.length();

 

    // Create and initialize DP table

    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 table (similar to LCS loops)

    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];

}

Read full article from Longest Repeating Subsequence - GeeksforGeeks