## Saturday, 19 September 2015

### Longest Repeating Subsequence

Find length of the longest repeating subsequence such that the two subsequence don’t have same string character at same position, i.e., any i’th character in the two subsequences shouldn’t have the same index in the original string.
Examples:
inputStr = "abc"
Output: 0

inputStr = "aab"
Output: 1
aab
aab

inputStr = "aabb"
Output: 2
a a b b
a a b b

if(inputChars[i-1]==inputChars[j-1] && i!=j) {
dp[i][j] = dp[i-1][j-1]+1;
} else {
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
}

package geeks.dp;

import java.io.IOException;

public class LongestRepeatingSubsequence {
public static void main(String[] args) throws IOException {
int length = inputChars.length;

int[][] dp = new int[length+1][length+1];
for (int i = 1; i <= length; i++) {
for (int j = 1; j <= length; j++) {
if(inputChars[i-1]==inputChars[j-1] && i!=j) {
dp[i][j] = dp[i-1][j-1]+1;
} else {
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
}
}
}
System.out.println(dp[length][length]);
}
}