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