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

         }

}