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.

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

• Invariant: dp[i][j] depends only on dp[i-1][j] and dp[i][j-1].
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

Trace (hand walkthrough)

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

Walk:
- true case: s3 "aadbbcbcac" picks a,a from s1, d,b,b from s2, then c,b,c,a,c in order -> valid
- false case: "aadbbbaccc" forces three b in a row, which cannot be matched by s1+s2 order -> invalid

Pitfalls to avoid

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

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.