Loading
Loading
A chat server receives keystrokes from two clients and writes them into one log as they arrive. Each client's keystrokes stay in their own order, but the two streams can be woven together in any way.
Given the two client streams and the server log, return true if the log could have been produced by interleaving the two streams: every character of both streams appears exactly once, and each stream's characters keep their relative order.
first = "abc", second = "xbz", merged = "axbbcz"a ← firstfirst: a|bcx ← second, b ← secondsecond: xb|zb ← first, c ← firstfirst finishedz ← secondboth streams used up exactlytrueSign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(m × n) time · O(n) space
Input. Run your code to watch it work on this input, one line at a time.
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
a from first, x and b from second, b and c from first, z from second.
Example 2
Second must give c before its a, but merged needs two a's before any c, and first has only one.