hardDynamic Programming 2DPure DSA~40 min
Interleave Two Event Streams
Two ordered event streams were merged into one combined log, each stream keeping its internal order. Given the two source streams and the merged log, decide whether the merge could have produced exactly that log.
Problem
Given strings s1, s2, and s3, return true if s3 can be formed by interleaving s1 and s2 while preserving the internal order of each. An interleaving uses all characters of both.
Input
Three strings s1, s2, s3 (lengths 0..100).
Output
A boolean: true if s3 is an interleaving of s1 and s2.
Constraints
- 0 ≤ |s1|, |s2| ≤ 100
- 0 ≤ |s3| ≤ 200
- Order within each source string must be preserved
Examples
Example 1
Input
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output
true
Characters can be drawn alternately from the two streams to spell s3.
Example 2
Input
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output
false
No interleaving order produces s3.