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
DP table stores subsequence lengths. - Backtracking reconstructs subsequence. - Together prints longest repeating subsequence. Conclusion: Shows how to print longest repeating subsequence using DP.