Shortest Common Carrier String
Medium2-D Dynamic Programming
Problem
A carrier of two strings first and second is a string that contains both of them as subsequences (each can be read in order by skipping some carrier characters).
Return the length of the shortest possible carrier.
Example 1
- Input:
- first = "stone", second = "tone"
- Output:
- 5
"stone" already contains "tone" as a subsequence.
Example 2
- Input:
- first = "bake", second = "eat"
- Output:
- 6
For example "bakeat": the two words share only one letter in a usable order.
Constraints
- 0 ≤ first.length, second.length ≤ 1000
- Both strings contain lowercase English letters only.
Hint
Show the first hint
Concatenating the strings always works. Which characters could the two words share in the carrier?
Walkthrough
How to approach it
01Clarify before coding
- Length only, or the string? Length only.
- Can a carrier character be used by both words? Yes, that is the whole point of sharing.
- Empty inputs? Allowed; the carrier is then the other string.
02Brute force
Recursively build the carrier from the front: on equal first characters emit one, otherwise try emitting either one, and take the shortest.
Cost: O(2^(m + n)) without memoisation.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.