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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class LongestRepeatingSubsequence {
public static void
main(String[] args) throws IOException {
BufferedReader
buffReader = new BufferedReader(
new InputStreamReader(System.in));
char[]
inputChars = buffReader.readLine().toCharArray();
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]);
}
}
No comments:
Post a Comment