Q35 Longest Repeating Subsequence | Practice | GeeksforGeeks
Mon Mar 27 2023 04:52:34 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
//{ Driver Code Starts
//Initial Template for Java
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine().trim());
while(T-->0)
{
String str = br.readLine().trim();
Solution ob = new Solution();
int ans = ob.LongestRepeatingSubsequence(str);
System.out.println(ans);
}
}
}
// } Driver Code Ends
//User function Template for Java
class Solution
{
public int LongestRepeatingSubsequence(String str)
{
/* Q35 dp playlist , finding Longest common subsequence in str with itself ,
and checking if equal characters have equal indexes or not as we need to find
repeated string with different characters
*/
int n = str.length() ;
int[][] dp = new int[n+1][n+1];
//last row ,last coloumn and last cell will be 0 by default
//handling for rest of the dp
for(int i = n-1 ; i>=0 ; i--){
for(int j = n-1 ; j>=0 ; j--){
//checking if chars are equal and indexes are not
if(str.charAt(i) == str.charAt(j) && i!=j)
dp[i][j] = dp[i+1][j+1] + 1;
else
dp[i][j] = Math.max(dp[i][j+1] , dp[i+1][j]);
}
}
return dp[0][0];
}
}
content_copyCOPY
https://practice.geeksforgeeks.org/problems/longest-repeating-subsequence2004/1
Comments