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

Related Posts Plugin for WordPress, Blogger...