Redirecting to
NADOS


  Prev   Next

Longest Repeating Subsequence







A bad workman blames his tools.

Longest Repeating Subsequence

Hey there. We start with a new question, "Longest Repeating Subsequence" in this article.

Before going further, we first want you to go through the problem's outline.


Important Links : Problem Link, Solution Video


Reader, the prerequisite of this problem is Longest Common Subsequence, so we suggest you go through it if you haven't already.

  • You are given a string str.
  • You have to find the length of the longest subsequence which is appearing twice in the string.
  • Every ith character in both the subsequences must have different indices in the original string.

Let the input string be "abacbc".

img

We see that "abc" is a repeating subsequence appearing as "a0b1c3" and "a2b4c5" such that no index of any character is the same in the 2 subsequences.

We are required to print the length of the longest such subsequence.

In the above example, "a0b1c3" and "a2b4c5" are invalid repeating subsequences because the index of the character 'a' in both the strings is the same which is not allowed.

WHAT

The approach we take is that we find the Longest Common Subsequence of the input string with itself such that there is no shared character of the same index in the 2 subsequences.

WHY

Reader, you already know "WHAT" we are going to do in this problem but it is important that you understand "WHY" we do it.

If we are given 2 strings such that s1= "abcd" and s2= "aebd", then their Longest Common subsequence (LCS) would have been "abd".

For finding out the LCS we first list all the subsequences of s1 and s2 and then find the common subsequences out of the two. Out of these, the subsequence with the longest length is our LCS.

Similarly, to find the Longest Repeating Subsequence (LRS), we list all the subsequences of the input string first. Then we find the common subsequences out of all the subsequences such that our condition of no same indexed character is fulfilled.

The repeating subsequence of the longest length is returned.

HOW

To solve the problem using the above approach we make a dp array as shown in figure 2.

img

Let's understand the above figure step by step.

  • A cell, say, dp[2][3] is assigned with the length of the LCS of the corresponding strings "a2c3b4c5" and "c3b4c5".
  • According to the meaning assigned, the LCS of a blank with any string does not exist. So we store 0 in the cells of the last row and last column.
  • NOTE 1: In the question of LCS, we have already discussed that for a cell if the characters at corresponding row and column are the same, then its value is one more than the element at the diagonal as shown in figure 3.
    img
  • NOTE 2: Also as shown in figure 4, if the 2 characters are not the same, then we stored the maximum value out of the cell to the right and to the bottom of the current cell.
    img
  • However, the above 2 points were followed when we didn't have the condition that no 2 characters should have the same index.
  • So, 2 characters follow the rule in NOTE 1 when they have the same character but different indices. Similarly, 2 characters follow the rule in NOTE 2 when they have the same character as well as the same indices.
  • According to the above explanation, the dp array is filled as shown in figure 2.
  • The desired answer is stored in the first cell dp[0][0] as it stores the LCS of "abacbc" with itself such that the given condition is fulfilled.
CODE

Reader, since you have already coded LCS, we are sure you will have no problem in coding this program.

Still, if you face any difficulties, just refer to the code given below.

import java.io.*; import java.util.*; public class Main { public static int solution(String str){ int[][]dp=new int[str.length()+1][str.length()+1]; for(int i=dp.length-1;i>=0;i--){ for(int j=dp[0].length-1;j>=0;j--){ if(i==dp.length-1 && j==dp[0].length-1){ dp[i][j]=0; }else if(i==dp.length-1){ dp[i][j]=0; }else if(j==dp[0].length-1){ dp[i][j]=0; }else{ if(str.charAt(i)==str.charAt(j) && i!=j){ dp[i][j]=dp[i+1][j+1]+1; }else{ dp[i][j]=Math.max(dp[i+1][j],dp[i][j+1]); } } } } return dp[0][0]; } public static void main(String[] args) { Scanner scn = new Scanner(System.in); String str = scn.next(); System.out.println(solution(str)); } }
java; true";
Analysis
Time Complexity:

O(n2)

Space Complexity:

O(n2)


We are done with the discussion of this problem. If you have any doubts we suggest you watch its solution video.

We'll see you in the next question.

Optimal Binary Search Tree
Dynamic Programming and Greedy
Author: Shreeya Gupta
 
Run
Id Name