Longest Repeated Subsequence

The problem, simply

You get one word. Pick a pattern of letters (in order, gaps allowed) and find it in the word two times. The two copies may share letters, but the k-th letter of copy 1 and the k-th letter of copy 2 must sit at different spots in the word.

Give back the length of the longest such pattern. This is the longest repeated subsequence.

A story to remember it

Picture it

Examples

Way 1: the simple way

Play LCS with the word against itself. f(i, j) is the answer when copy 1 may use the first i letters and copy 2 the first j letters.

1. If i == 0 or j == 0: 0.
2. If s[i - 1] == s[j - 1] and i != j: the twins grab these two flags, 1 + f(i - 1, j - 1).
3. Otherwise: max(f(i - 1, j), f(i, j - 1)).

The plain recursion asks the same (i, j) many times.

class Solution {
    public int longestRepeatedSubseq(String s) {
        return f(s, s.length(), s.length());
    }

    private int f(String s, int i, int j) {
        if (i == 0 || j == 0) return 0;
        if (s.charAt(i - 1) == s.charAt(j - 1) && i != j) {
            return 1 + f(s, i - 1, j - 1);           // same letter, different flags
        }
        return Math.max(f(s, i - 1, j), f(s, i, j - 1));
    }
}

How long it takes: up to two calls per step and about 2n steps deep, O(2^(2n)). Extra room: the call chain, O(n).

Way 2: the clever way

Make the (n + 1) by (n + 1) table, with the word down the side and the same word across the top. Fill it exactly like LCS, with one extra rule on a match.

1. Row 0 and column 0 are 0.
2. If the letters match and i != j, the box is the corner up and left, plus 1.
3. Otherwise, including every diagonal box, take the bigger of up and left.
4. The bottom right box is the answer.

class Solution {
    public int longestRepeatedSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == s.charAt(j - 1) && i != j) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;              // twins on different flags
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][n];
    }

    // Spell one longest repeated pattern by walking back.
    public String pattern(String s, int[][] dp) {
        StringBuilder sb = new StringBuilder();
        int i = s.length(), j = s.length();
        while (i > 0 && j > 0) {
            if (s.charAt(i - 1) == s.charAt(j - 1) && i != j) { sb.append(s.charAt(i - 1)); i--; j--; }
            else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
            else j--;
        }
        return sb.reverse().toString();
    }
}

How long it takes: n * n boxes, O(n^2). Extra room: the table, O(n^2), or two rows, O(n), if you only need the length. The table is symmetric, so you could also fill only half of it.

Watch out for

• The copies may overlap. In "axxzxy" index 2 is in both copies. Only the same letter in the same role is forbidden.
• Do not confuse this with "longest repeated substring", where the pattern has no gaps. That needs suffix arrays or the substring table.
• Off by one: box (i, j) compares s.charAt(i - 1) and s.charAt(j - 1).

What interviewers ask next

• Print the pattern: walk back from dp[n][n] as in pattern. On a match with i != j take the letter and go diagonal.
• Why is grabbing a match always safe? Any best answer can be changed to use these two flags as its last pair without breaking order, so taking it never loses.
• Does a string have any repeated subsequence of length 2 or more? Run this and check dp[n][n] >= 2. A letter that appears 3 or more times is a quick yes, since xx can then be picked twice.
• Longest repeated substring (no gaps): fill boxes with corner + 1 on a match with i != j, else 0, and take the max. Or use a suffix array with the LCP array in O(n log n).

Remember this

Grown-up words: the twins are the two subsequences, the score chart is the DP table, the forbidden diagonal is the i != j condition, and the whole problem is LCS(s, s) with that condition.