Print Longest Repeating Subsequence
This program prints longest repeating subsequence.
Problem Statement
Write a Java program to print longest repeating subsequence in "aabb".
Source Code
| 1 | public class PrintLongestRepeatingSubsequence { |
| 2 | public static void main(String[] args) { |
| 3 | System.out.println("Eduinq Print Longest Repeating Subsequence"); |
| 4 | String str="aabb"; |
| 5 | int n=str.length(); |
| 6 | int[][] dp=new int[n+1][n+1]; |
| 7 | for(int i=1;i<=n;i++){ |
| 8 | for(int j=1;j<=n;j++){ |
| 9 | if(str.charAt(i-1)==str.charAt(j-1) && i!=j) |
| 10 | dp[i][j]=1+dp[i-1][j-1]; |
| 11 | else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]); |
| 12 | } |
| 13 | } |
| 14 | int i=n,j=n; |
| 15 | StringBuilder lrs=new StringBuilder(); |
| 16 | while(i>0 && j>0){ |
| 17 | if(str.charAt(i-1)==str.charAt(j-1) && i!=j){ |
| 18 | lrs.insert(0,str.charAt(i-1)); |
| 19 | i--; j--; |
| 20 | } else if(dp[i-1][j]>dp[i][j-1]) i--; |
| 21 | else j--; |
| 22 | } |
| 23 | System.out.println("Longest repeating subsequence: "+lrs.toString()); |
| 24 | } |
| 25 | } |
Program Output
Eduinq Print Longest Repeating Subsequence Longest repeating subsequence: ab
Explanation
After the DP table for the longest repeating subsequence is built, backtracking from the last cell reconstructs the actual subsequence by following matching characters at different indices, printing the final repeating subsequence.