first and second. Find the shortest string from which each of them can be obtained by crossing out some characters (the remaining characters keep their order).
There are usually several such strings, so the answer is pinned down by the following rule. The string is built from the end, one letter at a time, until both words are used up. At each step, look at the last unused letters of both words:
1. if the last letter of first can be placed (counting it for first only) and the result can still be as short as possible, place it;
2. otherwise, if the last letter of second can be placed that way (for second only), place it;
3. otherwise the last letters of the two words are equal: place that letter and count it for both words.
Return the resulting string.first="cat", second="cut" → 'cuat'
The shared letters c and t are used once and only a and u remain, so the length is 4. Building from the end: t is shared by both words, then a from first, then u from second and the shared c. That gives cuat.
first="ab", second="ba" → 'bab'
Both aba and bab work. The last letter can be the b of first, so the answer is bab.
first="pine", second="pine" → 'pine'
The words are equal, and the word itself already contains both.
first and second consist of lowercase English lettersfirst="cat", second="cut"
'cuat'
Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.