Longest Repeating Subsequence

Find length of the longest repeating subsequence such that the two subsequences don’t have same string character at same position, i.e., any k’th character in the two subsequences shouldn’t have the same index in the original string.

This problem can be solved using the Longest Common Subsequence problem. LRS(str, str) where str is the input string with the restriction that when both the characters are same, they shouldn’t be on the same index in the two strings.

package amazon.dp;

public class LongestRptSubseq {

     private static int getLRS(String string) {

          

           char[] charArray = string.toCharArray();

           int len = charArray.length;

          

           int[][] dp = new int[len+1][len+1];

          

           for(int i=1;i<=len;i++) {

               

                for (int j=1;j<=len;j++) {

                     // If characters match and indexes are not same

                     if (charArray[i-1] == charArray[j-1] && i!=j) {

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

                          

                     } else {

                           // If characters do not match

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

                     }

                }

           }

          

           return dp[len-1][len-1];

     }

     public static void main(String[] args) {

           String string = "amazonazom";

           int len = getLRS(string);

           System.out.println("Longest Repeating Subsequence "+len);

     }

}