518. Common Subsequence of Three

Print the length of the longest subsequence common to all THREE given strings.

geeks, geeksfor, geeksforgeeks -> 5 geeks abc, def, ghi -> 0 abcd, acbd, adbc -> 2

## Why pairwise does not work

The tempting shortcut is to take the longest common subsequence of the first two strings and then of that with the third. It fails, and here is the case:

a = bab, b = bbcba, c = aba -> 2

The longest common subsequences of bab and bbcba are ba and bb, both of length 2. Intersect ba with aba and you get ba, length 2, which is the true answer. Intersect bb with aba and you get b, length 1, because aba holds only one b.

So the pairwise method is correct or wrong depending on which of two equally long intermediate results it happened to compute, and nothing in it chooses.

The error is relying on a non-unique intermediate result, and it is worth naming because it recurs well beyond this problem: composing two optimal answers does not generally give an optimal answer.

## Three dimensions

``` dp[i][j][k] = the longest subsequence common to the three prefixes of lengths i, j, k

a[i-1] == b[j-1] == c[k-1] -> dp[i][j][k] = dp[i-1][j-1][k-1] + 1 otherwise -> dp[i][j][k] = max( dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1] ) ```

The two-string recurrence with one more index and one more branch. Nothing conceptual is new, which is the point: the shape generalises and the COST is what changes.

## The cost, and why the constraints are small

Time and space are O(n m k). At 100 characters each that is 10^6, which is comfortable. At 1000 each it would be 10^9 entries, which is why the bound on this problem is 100 rather than the 2000 used elsewhere in this topic.

Reading the constraints and inferring the intended dimensionality is a skill in itself. A limit of 100 on three strings is a strong hint that a cubic table is expected, in the same way that a limit of 20 hints at 2^n and a limit of 10^5 rules out anything quadratic.

The space drops to O(m k) by keeping two layers, since only i and i-1 are live.

## The equality must be three-way

a[i-1] == b[j-1] == c[k-1], all three. Testing only two of them and taking the diagonal counts characters the third string does not have, and abc, def, ghi would answer more than 0.

## Boundaries

abc, def, ghi answer 0: nothing is shared.

a, a, a answer 1 and abc, abc, abc answer 3, the two ends of the range.

aaa, aa, a answer 1, limited by the shortest string.

Constraints - `1 ≤ length of each string ≤ 100` - all three contain only lowercase letters