You’re given three strings: s1, s2, and s3. Your task is to determine whether s3 can be formed by interleaving s1 and s2.

Interleaving means you take both strings and break them into smaller pieces (substrings), then merge those pieces while preserving the left-to-right order of characters within each original string.

The final mixed string might look like any of the following:

1. $s1_1 + s2_1 + s1_2 + s2_2 + \dots$

2. $s2_1 + s1_1 + s2_2 + s1_2 + \dots$

The pieces from s1 and s2 must appear in alternating segments, although either one is allowed to start first. The number of segments taken from each string should differ by at most one.

Constraints:

• $0 \leq$ s1.length, s2.length $\leq 100$

• $0 \leq$ s3.length $\leq 200$

• s1, s2, and s3 consist of lowercase English letters.

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.