Longest Repeating Subsequence

 Given a string str, 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.

 

Exampel 1:

Input: str = "axxxy"
Output: 2
Explanation: The longest repeating subsequenece
is "xx".

Example 2:

Input: str = "aab"
output: 1
Explanation: The longest reapting subsequenece
is "a".

method :

c++ implementation:

int LongestRepeatingSubsequence(string s)
{
	 int n=s.length();
	 int t[n+1][n+1];     
   
   
         for(int i=0;i<=n;i++)      
          t[i][0]=0;
      
         for(int j=0;j<=n;j++)
          t[0][j]=0;
      
     
         for(int i=1;i<=n;i++)
         {
           for(int j=1;j<=n;j++)
            {
               if(s[i-1]==s[j-1] && i-1!=j-1)           
                 t[i][j]=t[i-1][j-1]+1;
               else
                 t[i][j]=max(t[i-1][j],t[i][j-1]);
            }
         }
    
        return t[n][n];
}

Time Complexity: O(n2)

space Complexity: O(n2)