Find the longest common subsequence between two strings

The problem, simply

You get two strings, s1 of length n and s2 of length m. A subsequence is what is left after crossing out some letters, keeping the order. Find the length of the longest string that is a subsequence of both. This is the longest common subsequence, or LCS.

For ABCD and AEBD the answer is 3: ABD can be found in both, in order.

A story to remember it

Picture it

Examples

Way 1: the simple way

Look at the last letters of both strings.

1. If either string is empty, the answer is 0.
2. If the last letters match, they can end the common list: 1 + LCS of both strings without their last letters.
3. If not, at least one of them is not used. Try dropping the last letter of s1, then try dropping the last letter of s2, and keep the bigger answer.

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

    // longest common pick of the first i letters of s1 and first j letters of s2
    private int lcs(String s1, String s2, int i, int j) {
        if (i == 0 || j == 0) return 0;
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            return 1 + lcs(s1, s2, i - 1, j - 1);        // both last letters are used
        }
        return Math.max(lcs(s1, s2, i - 1, j),           // drop s1's last letter
                        lcs(s1, s2, i, j - 1));          // drop s2's last letter
    }
}

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

Way 2: the clever way

There are only (n + 1) * (m + 1) different (i, j) questions. Answer each one once in a chart, with s1 down the side and s2 across the top.

1. Row 0 and column 0 are 0, because an empty start shares nothing.
2. If letter i of s1 equals letter j of s2: box (i, j) is the box up and left plus 1.
3. Otherwise: box (i, j) is the bigger of the box above and the box to the left.
4. The answer is the bottom right box. To get the letters, walk back from it.

class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n + 1][m + 1];              // row 0 and column 0 stay 0
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;     // use both letters
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);   // skip one of them
                }
            }
        }
        return dp[n][m];
    }
}

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

Watch out for

• The chart is one bigger than the strings on each side. Compare s1.charAt(i - 1) with s2.charAt(j - 1).
• When the letters match, there is no need to also look at up and left. Using both letters is never worse.
• There can be several different longest lists of the same length. The walk back finds one of them. Ask whether any one is fine.

What interviewers ask next

• Print the letters? Start at the bottom right. On a match, keep the letter and go up left. Otherwise move to the bigger of up and left. Reverse the kept letters at the end.
• Use less room? Each row only needs the row above. Two rows of length m + 1 give O(min(n, m)) room if you put the shorter string across the top. Printing the letters in small room needs Hirschberg's trick.
• How is it linked to other problems? Fewest inserts and deletes to turn s1 into s2 is n + m - 2 * LCS. Shortest string that contains both as subsequences is n + m - LCS. Longest palindromic subsequence is the LCS of a string and its reverse. Note that edit distance with replace allowed is not given by this formula.
• What if one string has all distinct letters? Then LCS turns into the longest increasing subsequence of positions, which can be solved in O(n log n).
• Where is it used? The diff tool that shows changes between two files, and comparing DNA strands.

Remember this

Grown-up words: picks of letters in order are subsequences, the chart is a dynamic programming table, filling it from small to big is tabulation, and walking back from the corner is reconstructing the LCS.