Longest Common Subsequence

The problem, simply

You get two words. You may cross out any letters you like from each word, but you may not move letters around. After crossing out, both words must read exactly the same. How long can that shared word be?

The shared word is called a subsequence. Its letters keep their order but do not have to sit next to each other. Give back its length.

A story to remember it

Picture it

Examples

Way 1: the simple way

Look at the last letter of each word.

1. If either word is empty, the answer is 0.
2. If the two last letters are the same, keep that letter. The answer is 1 plus the answer for both words without their last letter.
3. If they differ, at least one of them is not in the shared word. Try dropping the last letter of the first word, then try dropping the last letter of the second word, and keep the bigger answer.

The trouble is that the two tries in step 3 soon ask the same small question again and again.

class Solution {
    // i and j are how many letters of each word we still look at
    public int lcs(String s1, String s2, int i, int j) {
        if (i == 0 || j == 0) return 0;                      // an empty word shares nothing
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            return 1 + lcs(s1, s2, i - 1, j - 1);            // keep the matching letter
        }
        return Math.max(lcs(s1, s2, i - 1, j),               // drop my last letter
                        lcs(s1, s2, i, j - 1));              // or drop yours
    }

    public int longestCommonSubsequence(String s1, String s2) {
        return lcs(s1, s2, s1.length(), s2.length());
    }
}

How long it takes: every mismatch splits into two calls, so in the worst case the calls double about m + n times, O(2^(m+n)). Extra room: the chain of waiting calls is at most m + n deep, O(m + n).

Way 2: the clever way

There are only (m + 1) * (n + 1) different small questions: "first i letters of word one against first j letters of word two". Write each answer in a table, a grid we call dp, and never work one out twice.

1. Make a table with one more row and one more column than the word lengths. Row 0 and column 0 stand for an empty word, so they hold 0.
2. Fill the table row by row, left to right.
3. If the letters for this row and this column match, the box is the box up and to the left, plus 1.
4. If they do not match, the box copies the bigger of the box above and the box to the left.
5. The bottom right box is the answer.

class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];   // row 0 and column 0 stay 0

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;              // corner plus one
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // best of up and left
                }
            }
        }
        return dp[m][n];
    }

    // Walk back through the table to spell one best shared word.
    public String buildLcs(String s1, String s2, int[][] dp) {
        StringBuilder sb = new StringBuilder();
        int i = s1.length(), j = s2.length();
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) { sb.append(s1.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: each of the m * n boxes is filled once with a few comparisons, O(m * n). Extra room: the table, O(m * n). Each row only reads the row above it, so two rows are enough if you only need the length, O(min(m, n)).

Watch out for

• Subsequence is not substring. Letters may have gaps between them. If gaps are not allowed, the mismatch box becomes 0 instead of copying a neighbor.
• On a match, do not also take the max with up and left. It is never bigger, but adding 1 to up or left is wrong.
• If you shrink to two rows, swap them after each row, or you read numbers from the wrong row.
• The memo version needs a table filled with -1 first, because 0 is a real answer.

What interviewers ask next

• Print the actual shared word, not just its length. Walk back from the bottom right box as in buildLcs: on a match take the letter and go diagonal, else go toward the bigger neighbor.
• Shortest common supersequence (the shortest word that contains both): its length is m + n - LCS.
• Fewest insertions and deletions to turn one word into the other: delete m - LCS letters and insert n - LCS.
• Longest palindromic subsequence: it is the LCS of a word and the same word reversed.
• Can you beat O(m * n)? Not in general. For special inputs, like two lists that are both orderings of the same distinct items, it turns into longest increasing subsequence and runs in O(n log n).

Remember this

Grown-up words: the sticker parade is the longest common subsequence (LCS), the score sheet is the DP table, filling it from small questions up is bottom up dynamic programming, the repeated calls are overlapping subproblems, and walking back is backtracking through the table.