This is the Java Program to Find the Length of the Longest Repeating Sub-sequence in a String.

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

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[i-1][j-1] + 1, otherwise maximum of L[i-1][j] and L[i][j-1]. Return L[n][n].

Here is the source code of the Java Program to Find the Length of the Longest Repeating Sub-sequence 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 Sub-sequence 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(i-1) == str.charAt(j-1) && i!=j){

M[i][j] = M[i-1][j-1] + 1;

`}`

`else`

`{`

M[i][j] = Math.max(M[i-1][j],M[i][j-1]);

`}`

`}`

`}`

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);

`}`

`}`

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(i-1) == str.charAt(j-1) && 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[i-1][j-1] + 1.

5. Otherwise, the length is updated as M[i][j] = Math.max(M[i-1][j],M[i][j-1]).

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.

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.**

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Check Programming Books
- Check Java Books
- Apply for Java Internship
- Practice Information Technology MCQs
- Apply for Computer Science Internship