Interleaving String Solution

Problem

Given two strings and a third string, determine whether the third is formed by interleaving the first two. An interleaving preserves the relative order of each source string's characters, but lets you pick from either string at every step.

Example:

Input: s1 = "ab", s2 = "cd", s3 = "acbd"
Output: true
Explanation: Take 'a' from s1, 'c' from s2, 'b' from s1, 'd' from s2 — each string's order is preserved.

Counter-example: s3 = "abdc" with the same s1 and s2 is false — 'd' appears before 'c' in s3, but s2 requires 'c' before 'd'.

Intuition

At every step you can take the next character from either s1 or s2, but a locally valid choice can lead to a dead end later — so greedy fails. The key insight is that k, the current position in s3, is always exactly i + j where i and j are how many characters you've consumed from s1 and s2. This means the state is just (i, j), and whether s3's first i+j characters are reachable by using s1's first i and s2's first j characters is a well-defined subproblem that can be filled in O(m·n).

Approach 1 — Recursion

At each step try consuming the next character from s1 or s2; since k = i + j is fully determined by the two pointers, the state is just (i, j). Without caching, the same (i, j) pairs are re-explored exponentially.

Steps:

Return false immediately if len(s1) + len(s2) ≠ len(s3).
Define dfs(i, j) where k = i + j is the current position in s3.
If i == len(s1) and j == len(s2), all characters matched — return true.
If s1[i] == s3[k], try advancing i and recurse.
If s2[j] == s3[k], try advancing j and recurse.
Return true if either branch succeeds, false otherwise.

1def isInterleave(s1: str, s2: str, s3: str) -> bool:
2    if len(s1) + len(s2) != len(s3):
3        return False
4
5    def dfs(i, j):
6        if i == len(s1) and j == len(s2):
7            return True
8        s3_pos = i + j  # position in s3 is always determined by how much of s1 and s2 we've used
9        if i < len(s1) and s1[i] == s3[s3_pos] and dfs(i + 1, j):
10            return True
11        if j < len(s2) and s2[j] == s3[s3_pos] and dfs(i, j + 1):
12            return True
13        return False
14
15    return dfs(0, 0)

Time: O(2^(m+n)) — each position in s3 can branch into two recursive calls with no result caching
Space: O(m+n) — recursion stack depth is at most m + n steps

Approach 2 — 2D Dynamic Programming

Build a table bottom-up: dp[i][j] is true if the first i + j characters of s3 can be formed using exactly the first i characters of s1 and the first j characters of s2.

Steps:

Return false immediately if len(s1) + len(s2) ≠ len(s3).
Create a (m+1) × (n+1) table initialized to false; set dp[0][0] = true.
Fill dp[i][0] for each i: whether s3's prefix of length i matches by consuming only s1.
Fill dp[0][j] for each j: whether s3's prefix of length j matches by consuming only s2.
For each (i, j): dp[i][j] is true if dp[i-1][j] is true and s1[i-1] == s3[i+j-1], or dp[i][j-1] is true and s2[j-1] == s3[i+j-1].
Return dp[m][n].

1def isInterleave(s1: str, s2: str, s3: str) -> bool:
2    m, n = len(s1), len(s2)
3    if m + n != len(s3):
4        return False
5
6    dp = [[False] * (n + 1) for _ in range(m + 1)]
7    dp[0][0] = True
8
9    for i in range(1, m + 1):
10        dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
11
12    for j in range(1, n + 1):
13        dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
14
15    for i in range(1, m + 1):
16        for j in range(1, n + 1):
17            s3_char = s3[i + j - 1]  # dp is 1-indexed, so the s3 position is i+j-1
18            dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3_char) or \
19                       (dp[i][j - 1] and s2[j - 1] == s3_char)
20
21    return dp[m][n]

Time: O(m·n) — one pass over an (m+1) × (n+1) table
Space: O(m·n) — the DP table; reducible to O(n) with a rolling row

Complexity Summary

Approach	Time	Space	When to use
Recursion	O(2^(m+n))	O(m+n)	Only to understand why caching is necessary
2D Dynamic Programming	O(m·n)	O(m·n)	Standard approach for any string interleaving problem

Common Mistakes

Skipping the length check: Without verifying len(s1) + len(s2) == len(s3) up front, the table's final cell can be false even when s3 has all the right characters in the wrong total count — or you risk accessing out-of-range s3 indices.
Using i + j instead of i + j - 1 for the s3 index: The dp table is 1-indexed over s1 and s2, so when filling dp[i][j], the matching character in s3 is at s3[i + j - 1], not s3[i + j]. This off-by-one silently shifts every comparison by one position.
Skipping first-row and first-column initialization: dp[i][0] and dp[0][j] depend on only one string and must be filled before the main double loop; leaving them false incorrectly marks all single-string prefixes as unachievable.
Allocating m × n instead of (m+1) × (n+1): The empty prefix case dp[0][0] requires indices starting at 0, and the final answer is at dp[m][n] — you need one extra slot in each dimension.
Swapping s1 and s2 in the transition: When extending from dp[i-1][j], you must compare s1[i-1] with s3[i+j-1]; comparing s2[j-1] there instead mixes up which string contributed the character that advanced i.

Interleaving String — Solution