Interleaving String

When both source strings can provide the next target character, a greedy pointer has to guess. Dynamic programming keeps both possibilities alive until the future proves one of them impossible.

Answer the contract first

We need to decide whether s3 can be formed by consuming every character of s1 and s2 exactly once while preserving the order within each source.

The sources may contribute runs of characters, not only alternating single characters. The first contribution can come from either source. The rules are:

• Characters taken from s1 must remain in their original order.
• Characters taken from s2 must remain in their original order.
• Every character from both sources must be used.

Start with the necessary length check:

len(s1) + len(s2) == len(s3)

If this fails, the answer is immediately False. The target cannot account for every source character.

Equal lengths are only a necessary condition. The target may still request a character that neither source can provide at the required point.

The solution direction is:

1. Track how many characters have been consumed from each source.
2. Derive the target position from those two counts.
3. Keep both source choices whenever both are locally possible.
4. Compute each repeated state once.
5. Compress the two-dimensional table only after its dependency structure is clear.

Empty strings fit this model naturally. If both sources are empty, the empty target is valid. If one source is empty, the target must equal the other source.

Why greedy pointers branch

Imagine two pointers, one into each source. At every target position, you can advance:

• s1 if s1[i] matches the next target character
• s2 if s2[j] matches the next target character

If only one source matches, the move is forced. The difficulty begins when both match.

Consider:

s1 = "aabc"
s2 = "abad"
s3 = "aabadabc"

At the first target character, both sources offer a.

Suppose a greedy rule always takes from s1 when possible:

Target position	Target character	Choice	Consumed state
0	a	take s1[0]	(1, 0)
1	a	take s1[1]	(2, 0)
2	b	take s1[2]	(3, 0)
3	a	take s2[0]	(3, 1)
4	d	no source matches	failure

At position 4, the next available characters are:

s1[3] = "c"
s2[1] = "b"

Neither is d. The target is valid, but this locally reasonable branch is dead.

A valid branch makes a different choice at the beginning:

Target position	Target character	Choice	Consumed state
0	a	take s2[0]	(0, 1)
1	a	take s1[0]	(1, 1)
2	b	take s2[1]	(1, 2)
3	a	take s2[2]	(1, 3)
4	d	take s2[3]	(1, 4)
5	a	take s1[1]	(2, 4)
6	b	take s1[2]	(3, 4)
7	c	take s1[3]	(4, 4)

The source-choice sequence is:

s2, s1, s2, s2, s2, s1, s1, s1

The lesson is precise: a local character match identifies a possible transition, not a correct decision.

A brute-force search would try both choices whenever they match. That produces a branching decision tree. Different branches can later reach the same pair of source positions, causing the search to solve the same future problem repeatedly.

That repeated subproblem is the leverage point. Once the state is defined by how much has been consumed from each source, the decision tree collapses into a grid of at most (m + 1)(n + 1) states.

Define the two-prefix state

Let:

m = len(s1)
n = len(s2)

Define:

dp[i][j]

as:

Whether the first i characters of s1 and the first j characters of s2 can form the first i + j characters of s3.

The state stores consumed-character counts, not zero-based source indices.

For example:

dp[2][3]

asks whether:

s1[:2]
s2[:3]

can form:

s3[:5]

The target position is forced:

target position = i + j

If i characters from s1 and j characters from s2 have already been consumed, exactly i + j target characters have been consumed. Therefore the next target character is:

s3[i + j]

There is no need for a third pointer.

At state (i, j), the exact history no longer matters. Every future possibility depends only on how many characters remain in each source.

Picture the states as a grid:

• Moving down consumes one character from s1.
• Moving right consumes one character from s2.
• Every path moves forward, so the original order inside both sources is preserved automatically.

A path from (0, 0) to (m, n) represents one possible interleaving. The problem asks whether at least one such path matches s3.

Derive the transitions and boundaries

The state dp[i][j] can be reached in at most two ways.

Consume from s1

If the final character of the selected prefixes came from s1, then:

• s1[i - 1] must match s3[i + j - 1].
• The predecessor dp[i - 1][j] must already be feasible.

So the s1 transition is valid when:

i > 0
s1[i - 1] == s3[i + j - 1]
dp[i - 1][j] is True

Consume from s2

Similarly, if the final character came from s2, then:

• s2[j - 1] must match s3[i + j - 1].
• The predecessor dp[i][j - 1] must already be feasible.

This transition is valid when:

j > 0
s2[j - 1] == s3[i + j - 1]
dp[i][j - 1] is True

The alternatives combine with OR:

dp[i][j] =
    (i > 0 and dp[i - 1][j] and s1[i - 1] == s3[i + j - 1])
    or
    (j > 0 and dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])

The base case is:

dp[0][0] = True

Two empty prefixes form an empty target prefix.

The first row can only consume from s2:

dp[0][j] depends on dp[0][j - 1]

The first column can only consume from s1:

dp[i][0] depends on dp[i - 1][0]

The offsets matter. i and j count consumed characters, while s1[i - 1] and s2[j - 1] access the most recently consumed source characters.

Prove the recurrence

A last-choice argument gives both necessity and sufficiency.

Suppose dp[i][j] is true. The final character of the formed target prefix must come from either s1 or s2.

Necessity

If the final character came from s1, it must be s1[i - 1]. That character must equal s3[i + j - 1], and the preceding target prefix must have been formed from:

s1[:i - 1] and s2[:j]

Therefore dp[i - 1][j] must be true.

If the final character came from s2, then s2[j - 1] must equal the final target character, and dp[i][j - 1] must be true.

Every valid construction must satisfy one of these two branches because the final character has only two possible sources.

Sufficiency

Now suppose the s1 branch is true:

dp[i - 1][j] is True
s1[i - 1] == s3[i + j - 1]

The predecessor forms the target prefix through position i + j - 2. Appending s1[i - 1] forms the next target character. Because the transition advances s1 by exactly one position, the order inside s1 remains intact.

The s2 branch works identically.

Thus every transition from a feasible predecessor creates a feasible current state. Every move consumes exactly one character from one source, so no path can reorder either source.

The final state is:

dp[m][n]

It is true exactly when all of s1 and all of s2 form all of s3.

Dry-run ambiguity and state convergence

Return to:

s1 = "aabc"
s2 = "abad"
s3 = "aabadabc"

At state (0, 0), both sources can supply the first target character a:

take s1[0] -> (1, 0)
take s2[0] -> (0, 1)

The next target character is also a. From either branch, the other source can supply it:

(0, 0) -> (1, 0) -> (1, 1)
(0, 0) -> (0, 1) -> (1, 1)

Both histories consume the same target prefix, "aa", and both arrive at (1, 1).

The histories differ. The future problem does not.

At (1, 1):

• s1[:1] has been consumed.
• s2[:1] has been consumed.
• The next target position is 1 + 1 = 2.
• The remaining feasibility question is identical regardless of which source supplied the first a.

This is why memoization works. It stores the answer for (1, 1) once instead of recomputing it for every history that reaches that state.

The same example also shows why a greedy pointer fails. One branch can consume s1 repeatedly and reach (3, 0), where the next target character is impossible. Another branch reaches (1, 4) and completes successfully. DP preserves both branches until their future behavior separates.

This is feasibility DP. Each state stores a Boolean: does any valid path reach this state? It does not count paths or reconstruct one. Those are different requirements and would require different output logic.

Implement compressed DP in Python

The full table mirrors the recurrence:

dp[i][j] depends on:
- dp[i - 1][j]  # top
- dp[i][j - 1]  # left

When processing rows from top to bottom, one row is enough:

• The previous value at dp[j] represents the top predecessor.
• The already-updated value at dp[j - 1] represents the left predecessor.

Because the sources are symmetric, make s2 the shorter source so the compressed dimension is as small as possible.

def is_interleave(s1: str, s2: str, s3: str) -> bool:
    if len(s1) + len(s2) != len(s3):
        return False

    # Keep the compressed dimension as small as possible.
    if len(s2) > len(s1):
        s1, s2 = s2, s1

    m, n = len(s1), len(s2)

    # Before each update, dp[j] represents the previous row's state.
    dp = [False] * (n + 1)
    dp[0] = True

    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 and j == 0:
                continue

            target_index = i + j - 1

            take_s1 = (
                i > 0
                and dp[j]  # top predecessor: dp[i - 1][j]
                and s1[i - 1] == s3[target_index]
            )

            take_s2 = (
                j > 0
                and dp[j - 1]  # left predecessor: dp[i][j - 1]
                and s2[j - 1] == s3[target_index]
            )

            dp[j] = take_s1 or take_s2

    return dp[n]

The overwrite order is the dangerous detail.

Before updating dp[j]:

• dp[j] still stores the top predecessor, dp[i - 1][j].
• dp[j - 1] already stores the current row's left predecessor, dp[i][j - 1].

Therefore both loops must move in increasing order. If the inner loop moved backward, or if dp[j] were overwritten before being read as the top state, the s1 transition would use the wrong value.

The one-dimensional invariant is:

Before assignment, dp[j] means the previous row's state. After assignment, it means the current row's state.

I would derive the two-dimensional version first in an interview, then compress it only after naming this invariant. Starting with the one-row implementation hides the dependency graph and makes an overwrite bug much harder to diagnose.

A top-down memoized search is another valid derivation. It uses the same (i, j) state and recursively tries both matching next characters. Its memoization space is O(mn). The bottom-up implementation above keeps the primary table at O(min(m, n)) space.

Complexity, edge cases, and interview checks

Let:

m = len(s1)
n = len(s2)

The full state grid contains (m + 1)(n + 1) cells. Each cell checks at most two transitions and performs constant work.

Therefore:

Time:  O(mn)
Space: O(min(m, n))

The source swap makes the compressed dimension the shorter source.

Check these cases explicitly:

Case	Required behavior
Both sources empty	Return True only for an empty target
One source empty	The target must equal the other source
Length mismatch	Return False immediately
Same lengths, impossible order	The length check passes; DP must reject
Repeated characters	Preserve both transitions when both match
Valid path uses the less obvious source	Do not commit greedily to the first match
Mismatch in the middle	The corresponding state becomes False

Common implementation errors:

• Maintaining an independent target pointer. Its position is always i + j.
• Checking only character counts. Counts ignore order.
• Returning after the first local match. A match is a possible transition, not proof of completion.
• Treating the problem as strict alternation between single characters. Valid interleavings can take several consecutive characters from one source.
• Mixing consumed counts with source indices. i is a count; s1[i - 1] is the last consumed character.
• Overwriting dp[j] before using its top-state meaning.
• Changing the Boolean state into a count or reconstructed path without changing the recurrence and output contract.

The transferable recognition rule is:

When a target is built by advancing through two ordered sources, and equal next symbols can make both sources viable, model the two consumed-prefix coordinates.

Then:

1. Derive the target index as their sum.
2. Make each transition consume exactly one source character.
3. Use OR for alternative feasible predecessors.
4. Prove that grid paths preserve source order.
5. Compress the table only after verifying what every overwritten cell means.

That is the reusable interleaving string DP pattern: two ordered inputs, one forced target position, and branching paths that become manageable when the state remembers both advances.