Longest Repeating Subsequence

Given a string, find length of the longest repeating subsequence such that the two subsequence don’t have same string character at same position, i.e., any ith character in the two subsequences shouldn’t have the same index in the original string.

Example:

str = abc, return 0, There is no repeating subsequence

str = aab, return 1, The two subsequence are a(first) and a(second).

Note that b cannot be considered as part of subsequence as it would be at same index in both.

str = aabb, return 2

Solution:

A modified version of Longest Common Subsequence. This question is equivlent to find the longest common subsequence between str and itself. When same characters appeared, we need to guaranty that they don't have same index.

Code:

public class Solution {

    public int longestRepeatingSubsequence(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        int n = str.length();

        //f stores the longest common subsequence between str(0, i) and str(0, j) 
        int[][] f = new int[n + 1][n + 1];

        //initialization: first row and first column are always zero.
        for (int i = 0; i <= n; i++) {
            f[0][i] = 0;
            f[i][0] = 0;
        }

        //function:
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                if (str.charAt(i - 1) == str.charAt(j - 1) && i != j) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                }
            }
        }

        return f[n][n];
    }
}