Two-dimensional Dynamic Programming
Two pointers into one table
When the third quantity you thought you needed is implied by the other two.
Key idea
The problem
Given two sources and a result, decide whether the result can be produced by taking characters from the two sources in order, using all of both.
The obvious state is three numbers: how much of each source is used, and how much of the result is built. That would be a three-dimensional table.
Why it works
The third number is not free
Every character of the result comes from exactly one source, so the amount of result built is always the sum of the two amounts consumed. The third index is determined by the first two and carries no information.
So the state is two numbers and the table is two-dimensional. Noticing that a candidate index is implied by the others is a general move worth looking for, and it is the difference here between a cubic table and a quadratic one.
Below, every pair of consumed amounts is listed with the result position it implies, which is the whole content of that observation.
Gotcha
Check the lengths first
If the lengths do not add up, no interleaving exists and the table indexing would read past the end of the result. The guard is one line and it is not optional.
It is also the fastest possible rejection. Cheap impossibility checks before building anything are worth making a habit, and this family of problems usually has one.
Why it works
Where the result index comes from
result[i + j - 1] is the character being matched, and it follows directly from the collapse: having consumed i and j characters, the next result position is i plus j, so the last one placed is one before that.
Deriving that expression rather than guessing it is what keeps the off-by-one straight. If the table indexes mean prefixes, the result index has to mean the same thing.
Cost
Cost
One cell per pair of prefixes, constant work each, so O(len(first) times len(second)) time and the same space, or one row with rolling updates.
The three-dimensional version would multiply that by the result length for no gain. Recognizing the implied index is the entire optimization and it is a state-design insight rather than a coding one.
Predict the output: why a greedy walk is not enough
Both sources start with the same character, so a walk that always prefers the first source has to guess. Type the two lines it prints.
Interleaving String
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.