512. The Smallest Longest Common Subsequence
Report the length of the longest common subsequence of two strings AND the subsequence itself.
Several subsequences can tie on length, so the answer is pinned: report the LEXICOGRAPHICALLY SMALLEST string among all longest common subsequences.
abcbdab, bdcaba -> 4, bcab
aab, aba -> 2, aa
abc, def -> 0
The second line is the case that needs the rule: aab and aba share aa and ab,
both of length 2, and aa is smaller.
## Why the usual backward walk will not do
Problem #237 fills dp[i][j] and the standard reconstruction walks BACKWARD from
dp[n][m], appending a character whenever the two current characters agree. That produces
SOME longest common subsequence, chosen by whichever branch the tie-break in the code
happens to take, and it builds the string in reverse.
Neither of those is compatible with wanting the smallest string, which has to be decided from the FRONT: the first character should be as small as possible, then the second, and so on.
## The suffix table
L[i][j] = the length of the longest common subsequence of a[i..] and b[j..]
filled from the bottom-right corner outward. Then build the answer forward:
i = 0, j = 0, remaining = L[0][0]
while remaining > 0:
for c = 'a' to 'z':
ia = first occurrence of c in a at or after i
jb = first occurrence of c in b at or after j
if both exist and 1 + L[ia+1][jb+1] == remaining:
emit c; i = ia+1; j = jb+1; remaining -= 1; break
## Why the earliest occurrence, and why the smallest letter
For a FIXED letter c, taking its earliest occurrence in each string is never worse:
L is non-increasing as the indices advance, so an earlier match leaves at least as much
of both strings available.
Given that, letter c can start a longest common subsequence of the remaining suffixes
exactly when 1 + L[ia+1][jb+1] equals the remaining length. Trying letters in
alphabetical order and taking the first that qualifies makes the leading character as
small as possible, and the same argument applies to the rest.
That is the same structure as problem #495: decide the answer front to back, with the table built in the opposite direction so each forward decision can be tested.
## Output shape
Print the length, then the subsequence, separated by a space. When the length is 0 print
0 alone, so no line is ever empty.
abc and def share nothing, and that is the test for it.
## Boundaries
cba and abc answer 1 a. Three letters in common, none in a compatible order, so the
best is one character, and the smallest such character is a.
xyz and zyx answer 1 x for the same reason with different letters, which checks that
the alphabetical scan is over letters rather than over positions.
abcd and badc answer 2 ac. Length 2 is reachable as ac, ad or bd, and ac
is the smallest.
## Cost
Time O(n m + 26 * answer) with the table dominating. Space O(n m), which reconstruction
requires: a rolling table cannot be walked.
Constraints - `1 ≤ length of a ≤ 2000` - `1 ≤ length of b ≤ 2000` - both contain only lowercase letters
Input
The first line contains the string a.
The second line contains the string b.
Output
Print the length of the longest common subsequence, then a space, then the lexicographically smallest such subsequence. Print 0 alone if there is no common subsequence.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.