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.