Interleaving String

Problem

Given three strings s1, s2, and s3, decide whether s3 can be formed by interleaving s1 and s2. An interleaving merges the two strings while preserving the internal order of each: at each step you take the next character from either s1 or s2, until both are exhausted.

Return True if some interleaving produces exactly s3, else False.

Examples

• s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" → True. The characters of s1 and of s2 each appear in their original order inside s3.
• s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" → False. No interleaving of the two produces this string.
• s1 = "", s2 = "", s3 = "" → True. Two empty strings interleave to the empty string.

Constraints

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• All strings consist of lowercase English letters.

If len(s1) + len(s2) != len(s3), the answer is immediately False. Otherwise the expected solution is O(m × n).

Think about it first

TL;DR

Reachability DP over (chars used from s1, chars used from s2) — O(m × n) time, O(n) space after rolling to one row.

Approach 1 — Brute-force recursion

Intuition: track how many characters have been consumed from each source, (i, j). Together they fix the position in s3 at i + j. To advance, take the next s3 character from s1 (if s1[i] matches) or from s2 (if s2[j] matches), and recurse. Success is reaching the end of both.

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

    def dfs(i: int, j: int) -> bool:
        if i == m and j == n:
            return True
        k = i + j
        if i < m and s1[i] == s3[k] and dfs(i + 1, j):
            return True
        if j < n and s2[j] == s3[k] and dfs(i, j + 1):
            return True
        return False

    return dfs(0, 0)

Complexity: O(2^(m+n)) time worst case (a two-way branch at each step), O(m+n) recursion depth.

Why the constraints break it: with m, n up to 100 the branch tree revisits the same (i, j) exponentially often.

Approach 2 — Top-down memoization

Insight: (i, j) fully determines the subproblem, and there are only (m+1)(n+1) distinct states. Cache them.

from functools import lru_cache


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

    @lru_cache(maxsize=None)
    def dfs(i: int, j: int) -> bool:
        if i == m and j == n:
            return True
        k = i + j
        if i < m and s1[i] == s3[k] and dfs(i + 1, j):
            return True
        if j < n and s2[j] == s3[k] and dfs(i, j + 1):
            return True
        return False

    return dfs(0, 0)

Complexity: O(m × n) time and space.

Approach 3 — Bottom-up 2-D table

Table meaning: dp[i][j] = can s3[:i+j] be built by interleaving s1[:i] and s2[:j]?

2-D recurrence:

dp[0][0] = True
dp[i][j] = ( dp[i-1][j] and s1[i-1] == s3[i+j-1] )   # last char came from s1
        or ( dp[i][j-1] and s2[j-1] == s3[i+j-1] )   # last char came from s2

Each cell depends only on its top and left neighbors, so the grid fills row by row, left to right:

flowchart LR
    U["dp[i-1][j]<br/>(last char from s1)"] --> C["dp[i][j]"]
    L["dp[i][j-1]<br/>(last char from s2)"] --> C

The first row and first column are the cases where only one source is used.

def isInterleave(s1: str, s2: str, s3: str) -> bool:
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for i in range(m + 1):
        for j in range(n + 1):
            k = i + j - 1
            if i > 0 and dp[i - 1][j] and s1[i - 1] == s3[k]:
                dp[i][j] = True
            if j > 0 and dp[i][j - 1] and s2[j - 1] == s3[k]:
                dp[i][j] = True
    return dp[m][n]

Walkthrough on s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac". Starting from dp[0][0] = True, consuming aa from s1 keeps the top-left corner reachable; d then forces a step into s2, and the table propagates a path of True cells toward dp[5][5], which is True. For the False example the reachable region never touches the far corner.

Complexity: O(m × n) time, O(m × n) space.

Approach 4 — Space-optimized rolling row

Insight: row i needs only row i-1 (dp[i-1][j]) and the current row’s left neighbor (dp[i][j-1]). A single 1-D array suffices: the not-yet-overwritten value at dp[j] still holds dp[i-1][j], the “from s1” contribution.

def isInterleave(s1: str, s2: str, s3: str) -> bool:
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False
    dp = [False] * (n + 1)
    dp[0] = True
    for j in range(1, n + 1):                 # row i = 0
        dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]
    for i in range(1, m + 1):
        dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
        for j in range(1, n + 1):
            k = i + j - 1
            from_s1 = dp[j] and s1[i - 1] == s3[k]        # old dp[j] = dp[i-1][j]
            from_s2 = dp[j - 1] and s2[j - 1] == s3[k]    # new dp[j-1] = dp[i][j-1]
            dp[j] = from_s1 or from_s2
    return dp[n]

Complexity: O(m × n) time, O(n) space.

Common pitfalls

• Skipping the length check. If len(s1) + len(s2) != len(s3) no interleaving exists, and without this guard the index math into s3 breaks.
• Greedy character picking. When both s1 and s2 offer the needed character, both branches must be considered; committing to one greedily produces wrong False results.
• The s3 index. The character placed at state (i, j) is s3[i + j - 1], not s3[i] or s3[j].
• The dp[0] boundary in the rolled version. Forgetting to update dp[0] per row (the all-s1 boundary) breaks cases where a long s1 run leads the interleaving.

Pattern takeaway

When two sequences merge while preserving the internal order of each, the state is how much of each has been consumed, and their sum indexes the target. This (i, j) reachability grid is the boolean version of edit distance and LCS: same grid, same “came from left or from above” transition, with a yes/no cell value instead of a count.