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.

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.

Note: Join free Sanfoundry classes at Telegram or Youtube
  2. //Java Program to Find the Length of the Longest Repeating Sub-sequence in a String
  4. import;
  5. import;
  7. public class LongestRepeatingSubsequence {
  8.     // Function to find the length of longest repeating subsequence
  9.     static int lengthOfLRS(String str){
  10.         int[][] M = new int[str.length()+1][strlength()+1];
  11.         for(int i=1;i<=str.length();i++){
  12.             for(int j=1;j<=str.length();j++){
  13.                 if(str.charAt(i-1) == str.charAt(j-1) && i!=j){
  14.                     M[i][j] = M[i-1][j-1] + 1;
  15.                 }
  16.                 else
  17.                 {
  18.                     M[i][j] = Math.max(M[i-1][j],M[i][j-1]);
  19.                 }
  20.             }
  21.         }
  22.         return M[str.length()][str.length()];
  23.     }
  24.     // Function to read user input and display the output
  25.     public static void main(String[] args) {
  26.         BufferedReader br = new BufferedReader(new InputStreamReader(;
  27.         String str;
  28.         System.out.println("Enter a string");
  29.         try{
  30.             str = br.readLine();
  31.         }catch (Exception e){
  32.             System.out.println("An error occurred");
  33.             return;
  34.         }
  35.         int x=lengthOfLRS(str);
  36.         System.out.println("The length of the longest repeating subsequence is "
  37.                                                                             + x);
  38.     }
  39. }
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(n2) where n is the length of the string.

Runtime Test Cases
Case 1 (Simple Test Case):
Enter a string
The length of the longest repeating subsequence is 3
Case 2 (Simple Test Case - another example):
Enter a string
The length of the longest repeating subsequence is 1

Sanfoundry Global Education & Learning Series – Java Programs.


Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.