LCS (Longest Common Subsequence) of three strings

The problem, simply

You get three words. Cross out letters from each word (without moving any) until all three read the same. How long can that shared word be?

It is the longest common subsequence (LCS) again, but with three words instead of two. 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. f(i, j, k) is the answer for the first i, j and k letters.

1. If any of i, j, k is 0, the answer is 0.
2. If all three last letters are the same, keep it: 1 + f(i - 1, j - 1, k - 1).
3. Otherwise, one of the three last letters is not used. Drop each one in turn and keep the best: max(f(i - 1, j, k), f(i, j - 1, k), f(i, j, k - 1)).

class Solution {
    public int lcsOf3(String a, String b, String c) {
        return f(a, b, c, a.length(), b.length(), c.length());
    }

    private int f(String a, String b, String c, int i, int j, int k) {
        if (i == 0 || j == 0 || k == 0) return 0;
        if (a.charAt(i - 1) == b.charAt(j - 1) && b.charAt(j - 1) == c.charAt(k - 1)) {
            return 1 + f(a, b, c, i - 1, j - 1, k - 1);   // all three agree
        }
        return Math.max(f(a, b, c, i - 1, j, k),          // drop from a
               Math.max(f(a, b, c, i, j - 1, k),          // drop from b
                        f(a, b, c, i, j, k - 1)));        // drop from c
    }
}

How long it takes: up to three calls per step and l + m + n steps deep, O(3^(l+m+n)). Extra room: the call chain, O(l + m + n).

Way 2: the clever way

There are only (l + 1) * (m + 1) * (n + 1) different questions. Store them in a 3D table dp[i][j][k]. Draw it as a stack of 2D sheets: sheet k is the usual LCS grid of s1 against s2, but where s3 may only use its first k letters.

1. Any box with i, j or k equal to 0 is 0.
2. If s1[i - 1], s2[j - 1] and s3[k - 1] are all equal, the box is the box one step back in all three (dp[i - 1][j - 1][k - 1], on the sheet before) plus 1.
3. Otherwise it is the biggest of up, left, and the same spot on the sheet before.
4. The answer is the last box of the last sheet.

class Solution {
    public int lcsOf3(String a, String b, String c) {
        int l = a.length(), m = b.length(), n = c.length();
        int[][][] dp = new int[l + 1][m + 1][n + 1];

        for (int i = 1; i <= l; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 1; k <= n; k++) {
                    if (a.charAt(i - 1) == b.charAt(j - 1) && b.charAt(j - 1) == c.charAt(k - 1)) {
                        dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;   // triple match
                    } else {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k],
                                      Math.max(dp[i][j - 1][k], dp[i][j][k - 1]));
                    }
                }
            }
        }
        return dp[l][m][n];
    }
}

How long it takes: one quick step per box, O(l * m * n). Extra room: the 3D table, O(l * m * n). Since layer i only reads layer i - 1, two 2D layers are enough, O(m * n).

Watch out for

• The mismatch case needs all three neighbors. Leaving one out can miss the answer.
• Match means all three letters equal. Writing a == b || b == c is a common slip.
• Memory: three words of length 200 make 8 million ints. Use two layers if memory is tight.

What interviewers ask next

• What about k words? The table has k dimensions and costs the product of the lengths. For many words the problem is NP hard in general.
• Save memory: keep only the layers for i - 1 and i, O(m * n) room.
• Print the shared word: walk back from dp[l][m][n]. On a triple match take the letter and step back in all three; otherwise step toward a neighbor with the same value.
• Use memo recursion instead? Yes, with a 3D memo filled with -1. It only visits reachable states, which can be fewer.

Remember this

Grown-up words: the shared dance is the longest common subsequence of three strings, the stack of sheets is a 3D DP table, and keeping only two sheets is the rolling array trick.