Space Optimized Solution of LCS

The problem, simply

You get two words, for example ABCBDAB and BDCAB. A subsequence is what you get by crossing out some letters and keeping the rest in order. Find the length of the longest subsequence that both words share. For these two words it is 4 (BCAB is one such word).

The usual answer fills a big table with one row per letter of the first word. Here the goal is to get the same answer while storing only a tiny part of that table.

A story to remember it

Picture it

Examples

Way 1: the simple way

Fill the full table. dp[i][j] is the answer for the first i letters of s1 and the first j letters of s2.

1. Row 0 and column 0 are 0 (an empty word shares nothing).
2. If the letters match, dp[i][j] = dp[i-1][j-1] + 1, the corner plus one.
3. If not, dp[i][j] = max(dp[i-1][j], dp[i][j-1]), the bigger of above and left.
4. The answer is dp[m][n].

class Solution {
    public int lcs(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        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;              // match: corner + 1
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // bigger of above and left
                }
            }
        }
        return dp[m][n];
    }
}

How long it takes: one step per cell, O(m * n). Extra room: the whole table, O(m * n). Two words of 10,000 letters need 100 million cells, which is about 400 MB of ints.

Way 2: the clever way

Each cell reads from three places: above, above left, and left. Above and above left are in the previous row. Left is in the row you are writing. So two rows are enough.

1. Make the shorter word the columns, so each row is as short as possible.
2. Keep prev (the row above) and curr (the row being filled).
3. Fill curr with the same rule as before, reading prev for above and corner.
4. After each row, swap them: curr becomes prev, and the old prev is reused as the new curr.

class Solution {
    public int lcs(String s1, String s2) {
        if (s1.length() < s2.length()) {        // make s2 the shorter word
            String t = s1; s1 = s2; s2 = t;
        }
        int m = s1.length(), n = s2.length();
        int[] prev = new int[n + 1];            // the row above
        int[] curr = new int[n + 1];            // the row we are writing
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    curr[j] = prev[j - 1] + 1;                   // corner + 1
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);    // above or left
                }
            }
            int[] t = prev; prev = curr; curr = t;  // slide down
        }
        return prev[n];                          // after the last swap, prev is the last row
    }
}

How long it takes: still one step per cell, O(m * n). Extra room: two rows of the shorter word's length, O(min(m, n)).

Way 3: one row and a saved corner

You can even use one row. Write the new row on top of the old one, from left to right. The only problem is the corner: by the time you need dp[i-1][j-1], you have already overwritten it. So save it in a variable before you overwrite each cell.

class Solution {
    public int lcs(String s1, String s2) {
        if (s1.length() < s2.length()) {
            String t = s1; s1 = s2; s2 = t;
        }
        int m = s1.length(), n = s2.length();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            int corner = 0;                      // dp[i-1][j-1], saved before it is lost
            for (int j = 1; j <= n; j++) {
                int above = dp[j];               // still the old row's value
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[j] = corner + 1;
                } else {
                    dp[j] = Math.max(above, dp[j - 1]);
                }
                corner = above;                  // becomes the corner for column j + 1
            }
        }
        return dp[n];
    }
}

Same O(m * n) time, and only n + 1 numbers plus one saved corner.

Watch out for

• In the one row version, forgetting to save the corner. Then a match reads the new value instead of the old one, and answers come out too big.
• Forgetting to reset corner = 0 at the start of each row. Column 0 is always 0, so the corner must start at 0 again, or a value from the previous row leaks in.
• Pick the shorter word for the columns, or the room used is the longer word's length.
• With two rows you can only get the length. To print the actual subsequence you need more (see below).

What interviewers ask next

• Can you print the subsequence with little memory? Yes, with Hirschberg's trick. Split the first word in half, run the two row pass forward on the top half and backward on the bottom half, find the best split column, and recurse on the two halves. Time stays O(m * n) and room is O(min(m, n)).
• Does this trick work for edit distance too? Yes. Edit distance reads the same three neighbors, so the same two rows work.
• What about three words? The table is 3D, and you can keep two 2D layers instead of the whole cube.
• When is LCS faster than O(m * n)? When letters are rare. Special methods based on matching pairs (Hunt and Szymanski) are fast when few letters match.

Remember this

Grown-up words: crossing out letters gives a subsequence, the chart is the LCS dynamic programming table, keeping two lines is the rolling array trick, the saved corner is the diagonal variable, and the halving trick is Hirschberg's algorithm.