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

}

## No comments:

## Post a Comment