Find Longest Repeating Subsequence

This program finds longest repeating subsequence.

Problem Statement

Write a Java program to find longest repeating subsequence in "aabebcdd".

Source Code

1 public class LongestRepeatingSubsequence {
2 public static void main(String[] args) {
3 System.out.println("Eduinq Longest Repeating Subsequence");
4 String str="aabebcdd";
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 System.out.println("Length of LRS = "+dp[n][n]);
15 }
16 }

Program Output

Eduinq Longest Repeating Subsequence
Length of LRS = 3

Explanation

DP table compares characters at different indices. - Condition ensures subsequence repeats but not same index. - Together finds longest repeating subsequence. Conclusion: Shows how to find longest repeating subsequence.

Quick Links to Explore