Interleaving String

Problem

Given three strings s1, s2, and s3, decide whether s3 can be formed by merging s1 and s2 so that every character of both is used exactly once and the characters of each original string appear in s3 in their original relative order. The two sources may alternate arbitrarily.

• Each of the two source strings is up to 120 characters.
• The combined target string is up to 240 characters.
• All strings consist of lowercase English letters.

Examples

• s1 = "xxbcc", s2 = "dccbx", s3 = "xdxccbcbcx" → true. One valid split is x|d|x|cc|bc|b|c|x with segments alternating between s1 and s2.
• s1 = "xxbcc", s2 = "dccbx", s3 = "bcxxbccdcx" → false. s3 starts with b, but neither s1 nor s2 begins with b, so no interleaving can produce this string.
• s1 = "", s2 = "", s3 = "" → true. Three empty strings interleave trivially.

Hints

1. Suppose you have used the first i characters of s1 and the first j characters of s2. Which position of s3 are you at? Which character must come next?
2. When s1[i] and s2[j] are both equal to the next character of s3, you cannot decide greedily. Keep both options alive.
3. dp[i][j] = can s3[:i+j] be formed from s1[:i] and s2[:j]. Each cell comes from the cell above or the cell to the left.