Interleaving String in C++

You get three strings, s1, s2 and s3.

Return true if s3 is an interleaving of s1 and s2. Otherwise, return false.

An interleaving mixes two strings into one. It uses every letter of both strings exactly once. The letters of s1 keep their order, and so do the letters of s2.

Example 1:

Input: s1 = "dog", s2 = "cat", s3 = "dcaotg"
Output: true
Explanation: Read s3 from left to right:
d comes from s1,
c and a come from s2,
o comes from s1,
t comes from s2,
g comes from s1.

Example 2:

Input: s1 = "dog", s2 = "cat", s3 = "dotcag"
Output: false
Explanation: Only s2 has a t.
In s2, the t comes after the c and the a.
In s3, the t comes before them.

Example 3:

Input: s1 = "ab", s2 = "ac", s3 = "acab"
Output: true
Explanation: Both strings start with an a.
The first a of s3 must come from s2.
If it came from s1, the c could not come next.
The last two letters, a and b, come from s1.

Constraints:

• s1 has 0 to 1,000 letters.
• s2 has 0 to 1,000 letters.
• s3 has 0 to 2,000 letters.
• All letters are lowercase English letters.