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

Example 1:

Input:"aab"
Output:1
Explanation:
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.

Example 2:

Input:"abc"
Output:0
Explanation:
There is no repeating subsequence

Solution:
A two-sequence DP problem. 
dp[i][j] means the first i chars and first j chars the longest length of common subsequences.

Code (Java):

public class Solution {
    /**
     * @param str: a string
     * @return: the length of the longest repeating subsequence
     */
    public int longestRepeatingSubsequence(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        
        int n = str.length();
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j && str.charAt(i - 1) == str.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        
        return dp[n][n];
    }
}