Merging Two Trains
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Two freight trains merge onto one track. Each car carries a one-letter cargo code; reading the first train from the front gives
s1, the second gives s2.
While merging, the front-most remaining car of either train is detached and appended to the new train, again and again, until every car of both trains has been used exactly once. So the cars of each train keep their relative order.
Given s3, the codes of the merged train from the front, return true if s3 can be produced from s1 and s2 this way,
otherwise false.
Examples
| s1 | s2 | s3 | result |
|---|---|---|---|
"aabcc" | "dbbca" | "aadbbcbcac" | true |
"aabcc" | "dbbca" | "aadbbbaccc" | false |
"ab" | "cd" | "abcde" | false |
Example 1 — Take "aa" from s1, "dbbc" from s2, "bc" from s1, "a" from s2, then "c" from s1.
Example 2 — No order of taking cars produces s3.
Example 3 — The lengths do not match; s3 must use exactly all cars of both trains.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(s1: string, s2: string, s3: string) → bool
Constraints
-
s1.length -
s2.length -
s3.length - All three strings consist of lowercase English letters only.
Expected complexity
- Time
- O(NM)
- Space
- O(M)
Examples
| s1 | s2 | s3 | Expected |
|---|---|---|---|
"aabcc" | "dbbca" | "aadbbcbcac" | true |
"aabcc" | "dbbca" | "aadbbbaccc" | false |
"ab" | "cd" | "abcde" | false |
Hint
Hint
If the lengths do not add up, answer false. After taking i cars from s1 and j from s2 the merged train must equal the
first i + j letters of s3, so (i, j) is the whole state:
ok[i][j] = (ok[i-1][j] and s1[i-1] == s3[i+j-1]) or (ok[i][j-1] and s2[j-1] == s3[i+j-1]).
Branching recursion explodes on inputs like "aaa…a"; filling the table is .
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 14 | verdict only |
| performance | 60 | 4 | verdict only |