This is the Java Program to Find the Length of the Longest Repeating Subsequence in a String.
Problem Description
Given a string s, find and print the length of the longest repeating subsequence in the string, that is, the length of the subsequence consisting of some of the characters in the original string, which are present in two different locations in the string and in the same order.
Example:
String str =”HELLO”;
Output = 1
Problem Solution
In this question, take care that the character in the same position, should not be counted in longest repeated subsequence. Create a matrix of size (n+1) * (n+1) and initialize its first row and column as zero. Now, using nested loops to check if the characters at different indexes match if they do increment the current value as follows L[i][j] = L[i1][j1] + 1, otherwise maximum of L[i1][j] and L[i][j1]. Return L[n][n].
Program/Source Code
Here is the source code of the Java Program to Find the Length of the Longest Repeating Subsequence in a String. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.


//Java Program to Find the Length of the Longest Repeating Subsequence in a String


import java.io.BufferedReader;

import java.io.InputStreamReader;


public class LongestRepeatingSubsequence {

// Function to find the length of longest repeating subsequence

static int lengthOfLRS(String str){

int[][] M = new int[str.length()+1][strlength()+1];

for(int i=1;i<=str.length();i++){

for(int j=1;j<=str.length();j++){

if(str.charAt(i1) == str.charAt(j1) && i!=j){

M[i][j] = M[i1][j1] + 1;

}

else

{

M[i][j] = Math.max(M[i1][j],M[i][j1]);

}

}

}

return M[str.length()][str.length()];

}

// Function to read user input and display the output

public static void main(String[] args) {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String str;

System.out.println("Enter a string");

try{

str = br.readLine();

}catch (Exception e){

System.out.println("An error occurred");

return;

}

int x=lengthOfLRS(str);

System.out.println("The length of the longest repeating subsequence is "

+ x);

}

}
Program Explanation
1. In function lengthOfLRS(), a new matrix of size (n+1)*(n+1) is created, where n is the length of the string.
2. The set of nested loops for(i=1; i<n; i++) { for(j=1; j<n; j++) are used to match the characters at different positions.
3. The condition if(str.charAt(i1) == str.charAt(j1) && i!=j), checks whether the characters at different positions are equal.
4. If they are, then the length of longest repeated subsequence upto current indices i and j is updated as M[i][j] = M[i1][j1] + 1.
5. Otherwise, the length is updated as M[i][j] = Math.max(M[i1][j],M[i][j1]).
6. The value M[n][n] is finally returned as the length of the longest repeated subsequence.
Time Complexity: O(n^{2}) where n is the length of the string.
Runtime Test Cases
Case 1 (Simple Test Case): Enter a string AABEBCDD The length of the longest repeating subsequence is 3 Case 2 (Simple Test Case  another example): Enter a string Hello The length of the longest repeating subsequence is 1
Sanfoundry Global Education & Learning Series – Java Programs.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!