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

This is the Java Program to Find the Length of the Longest Repeating Sub-sequence 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[i-1][j-1] + 1, otherwise maximum of L[i-1][j] and L[i][j-1]. Return L[n][n].

Program/Source Code

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

```
    }
```
```
}
```

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(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²) where n is the length of the string.

Note: Join free Sanfoundry classes at Telegram or Youtube

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.

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

« Prev - Dutch National Flag Problem in Java

» Next - Java Program to Find the Sum of the Series 1/1+1/2+1/3+…1/N

Related Posts:

Recommended Articles: