Recognize an Order-Preserving Merge of Two Strings
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Determine whether `s3` can be formed by interleaving all characters of `s1` and `s2`, preserving each input's internal character order. Equivalently, split each input into consecutive nonempty chunks and alternate chunks from the two inputs, starting with either; their chunk counts differ by at most one. Empty input strings are allowed.
Return a boolean. Every character from both inputs must be used exactly once, so a length mismatch makes the answer false.
```cpp
bool isInterleave(string s1, string s2, string s3);
```
### Examples
```text
Input: s1 = "ab", s2 = "ac", s3 = "aabc"
Output: true
```
The characters can come from the first, second, first, then second input.
```text
Input: s1 = "ab", s2 = "cd", s3 = "adbc"
Output: false
```
Although all letters are present, the second input's `c` cannot appear after its `d`.
### Constraints
- `0 <= s1.length,s2.length <= 100`.
- `0 <= s3.length <= 200`.
- All characters are lowercase English letters.
### Source follow-up
Use only `O(s2.length)` additional memory, apart from constant bookkeeping.
Overview: Check an order-preserving interleaving of two complete strings with length validation and the source’s linear-memory follow-up.
