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.

Quick Links to Explore