Find Longest Recurring Subsequence in String

The problem, simply

You get one string. Pick some letters in order (you may skip letters) to spell a word, then pick letters again to spell the same word a second time. The two picks may never use the same spot for the same letter of the word.

Give back the length of the longest word you can spell twice like that. This is the longest repeating subsequence.

A story to remember it

Picture it

Examples

Way 1: the simple way

Let f(i, j) be the answer when copy 1 may use only the first i letters and copy 2 only the first j letters. Look at letter i of copy 1 and letter j of copy 2.

1. If either copy has no letters left, the answer is 0.
2. If the two letters are equal and they are at different spots (i != j), use them: 1 + f(i - 1, j - 1).
3. Otherwise skip a letter in one copy or the other and keep the better: max(f(i - 1, j), f(i, j - 1)).

class Solution {
    public int longestRepeatingSubsequence(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 spots
        }
        return Math.max(f(s, i - 1, j), f(s, i, j - 1)); // skip one letter
    }
}

How long it takes: every mismatch splits in two and the depth is up to 2n, so up to O(4^n). The same (i, j) is solved many times. Extra room: the call stack, O(n).

Way 2: the clever way

There are only (n + 1) * (n + 1) different (i, j) questions. Put them in a chart with the string down the side (copy 1) and across the top (copy 2), and fill it row by row.

1. Row 0 and column 0 are 0.
2. For box (i, j): if the letters match and i != j, take the box up and left plus 1.
3. Otherwise take the bigger of the box above and the box to the left.
4. The slant boxes (i, i) pair a letter with its own spot, so they never count as a match.
5. The answer is the bottom right box.

class Solution {
    public int longestRepeatingSubsequence(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;          // match at two different spots
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][n];
    }
}

How long it takes: n * n boxes, each in constant time, O(n^2). Extra room: the chart, O(n^2).

Watch out for

• The rule is about spots, not letters. aa is fine because the two a's sit at different spots.
• Chart boxes talk about the first i letters, so compare s.charAt(i - 1) and s.charAt(j - 1).
• Do not confuse this with the longest repeated substring, where the letters must be next to each other. That needs a different method, like a suffix array or binary search with hashing.

What interviewers ask next

• Print the repeated word, not just its length? Start at the bottom right box. If the letters match with i != j, take that letter and go up left. Otherwise go to the bigger of up and left. Reverse what you collected.
• Can you use less room? Each row only needs the row above it, so two rows of length n + 1 give O(n) room.
• Longest repeated substring (no gaps)? Change the rule: on a match with i != j take up left plus 1, otherwise 0, and keep the biggest box seen. The pieces must not overlap if the interviewer says so, which adds the check dp[i - 1][j - 1] < j - i.
• Why does the chart stay symmetric? Box (i, j) and box (j, i) ask the same question with the copies swapped, so you could fill only half of it.

Remember this

Grown-up words: the picks are subsequences, the chart is a dynamic programming table, matching the string against itself is a self LCS, and the slant boxes are the main diagonal of the table.