Interleaving String

Given strings s1, s2, and s3, determine if s3 is formed by interleaving s1 and s2 while preserving the order of characters in each. Brute-force recursion is exponential.

Why this is worth learning

A state records how many bytes have been consumed from each source. Their sum fixes the target position, so no third DP dimension is needed.

Before coding: one-minute experiment

For s1="ab", s2="ac", and s3="acab", why can committing to the first matching source at the initial "a" fail?

Function signature

func IsInterleave(s1, s2, s3 string) bool

Inputs / outputs

• s1, s2, s3: input strings.
• Return: true if s3 is an interleaving of s1 and s2.

Example

s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" -> true
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" -> false

Constraints

• 0 <= len(s1), len(s2) <= 200

Core idea (near-solution)

2D DP where dp[i][j] is true if s1[:i] and s2[:j] can form s3[:i+j].

Invariant: dp[i][j] depends only on dp[i-1][j] and dp[i][j-1].

Algorithm (step-by-step)

1. If len(s1)+len(s2) != len(s3), return false.
2. Initialize dp[0][0] = true.
3. Fill first row/column using matches against s3.
4. For each i, j:
   • dp[i][j] is true if either:
     • dp[i-1][j] and s1[i-1] == s3[i+j-1], or
     • dp[i][j-1] and s2[j-1] == s3[i+j-1].
5. Return dp[m][n].

Correctness sketch

Let I(i,j) mean s1[:i] and s2[:j] can form s3[:i+j] while preserving each source order. The empty pair forms the empty target. A nonempty interleaving ends either with s1[i-1] from a reachable I(i-1,j), or with s2[j-1] from a reachable I(i,j-1), and the chosen byte must match s3[i+j-1]. These alternatives are exhaustive and either constructs a valid interleaving. Length mismatch is impossible before DP starts. Left-to-right row updates preserve old top and new left reachability, so the rolled recurrence computes the full table’s result.

Trace (hand walkthrough)

Let s1="aabcc" and s2="dbbca". For target "aadbbcbcac", one valid source sequence is:

target: a a d b b c b c a c
source: 1 1 2 2 2 2 1 1 2 1

Reading only source-1 positions gives aabcc; reading source-2 positions gives dbbca, so both orders are preserved.

For target "aadbbbaccc", prefix aadbbb is feasible: it consumes aab from s1 and dbb from s2. Its only consumed-count state is (i,j)=(3,3). Both next source bytes are now c, but the next target byte is a. No transition can form prefix aadbbba, so this target fails. The three consecutive b bytes are not the reason for failure.

Pitfalls to avoid

• Skipping the length check.
• Off-by-one in s3 index (i+j-1).

Debugging lens

Test length mismatch, one empty source, repeated shared prefixes, and equal character counts with the wrong order. Frequency equality is necessary but does not establish interleaving.

Complexity

• Time: O(m*n).
• Extra space: O(n) with rolling array.

Implementation notes (Go)

• Use a 1D dp slice and update left-to-right for each i.

Contract precision

All lengths and positions use byte semantics. Source order must be preserved independently even when identical bytes occur in both strings.

Reconstruction checkpoint

For s1="ab", s2="ac", and s3="acab", why can committing to the first matching source at the initial "a" fail?

Model answer

Taking the first a from s1 leaves b and a as the next source bytes, neither matching target c. Taking a then c from s2, followed by a then b from s1, succeeds. Equal available bytes require preserving both possible states.

Return to 2D DP · Module quiz