Two Streams, One Merge
Medium2-D Dynamic Programming
Problem
Two sensors emit character streams left and right. A logger merges them into merged by repeatedly taking the next character from one stream or the other, never reordering characters within a stream, until both are exhausted.
Return true if merged could have been produced this way from left and right, and false otherwise.
Example 1
- Input:
- left = "abc", right = "xy", merged = "axbyc"
- Output:
- true
Take a (left), x (right), b (left), y (right), c (left).
Example 2
- Input:
- left = "ab", right = "ab", merged = "abba"
- Output:
- false
After "ab" from one stream the other still starts with "a", so the merge cannot continue with "b".
Example 3
- Input:
- left = "ab", right = "cd", merged = "acdbx"
- Output:
- false
The lengths do not even add up.
Constraints
- 0 ≤ left.length, right.length ≤ 200
- 0 ≤ merged.length ≤ 400
- All strings contain lowercase English letters only.
Hint
Show the first hint
A greedy 'take from whichever stream matches' fails when both streams offer the same character. You need to remember how far you got in each stream.
Walkthrough
How to approach it
01Clarify before coding
- Must every character of both streams be used? Yes, and nothing else may appear in merged, so the lengths must add up.
- Can streams be empty? Yes; then merged must equal the other stream.
- Can the same character appear in both streams? Yes, which is exactly what defeats greedy.
02Brute force
Recursively match merged one character at a time, branching into left or right whenever both fit.
Cost: O(2^(m + n)) when both streams share characters (e.g. 'aaaa…' vs 'aaaa…').
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.