30. Longest repeating subsequence

30 .Longest repeating subsequence
Video Link : https://youtu.be/hbTaCmQGqLg
GFG Practice Link: https://practice.geeksforgeeks.org/problems/longest-repeating-subsequence2004/1

Approach : i). make another copy of the string 
ii). now find the LCS with the condition that characters should have not same index i.e if str1[i-1]==str2[j-1] then i != j .
iii). Now return the length of LCS . 

                  ------->>>>>>>>>>>------------>>>>>>>>>>>>________CODE________<<<<<<<<<<<<------------<<<<<<<<<<<<<<<<<<<<<<<<<<<

//{ Driver Code Starts
#include<bits/stdc++.h>
using namespace std;

// } Driver Code Ends
class Solution {
	public:
		int LongestRepeatingSubsequence(string str){
		    // Code here
		    
		    int n= str.size();
		    string a=str; 
		    
		    vector<vector<int>> dp (n+1, vector<int> ( n+1));
		    
		    for(int i=0;i<n+1;i++)
		    {
		        dp[i][0]=0;
		    }
		    for(int i=0;i<n+1;i++)
		    {
		        dp[0][i]=0;
		    }
		    
		    
		    for(int i=1;i<n+1;i++)
		    {
		        for(int j=1;j<n+1;j++)
		        {
		            
		            if(str[i-1]==a[j-1] && 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[n][n]; 
		    
		}

};

//{ Driver Code Starts.
int main(){
	int tc;
	cin >> tc;
	while(tc--){
		string str;
		cin >> str;
		Solution obj;
		int ans = obj.LongestRepeatingSubsequence(str);
		cout << ans << "\n";
	}
	return 0;
}
// } Driver Code Ends