Interleaving String

Problem

Given three strings s1, s2, and s3, decide whether s3 can be formed by interleaving s1 and s2. An interleaving weaves the two strings together while keeping the internal order of each one intact — you repeatedly take the next character from either s1 or s2 until both are exhausted.

Return True if such an interleaving produces exactly s3, else False.

Examples

• s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" → True — one weave: aa(s1) dbbc(s2) b(s1) c(s1)… the characters of each source appear in order inside s3.
• s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" → False — no weave of the two produces this string.
• s1 = "", s2 = "", s3 = "" → True — two empty strings interleave to empty.

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 you’ve consumed from each source, (i, j). Together they pin the position in s3 to 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.

class Solution:
    def isInterleave(self, 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 (two-way branch each step), O(m+n) depth.

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

Approach 2 — Top-down memoization

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

from functools import lru_cache


class Solution:
    def isInterleave(self, 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

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

class Solution:
    def isInterleave(self, 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". dp[0][0] = True; consuming aa from s1 keeps the top-left corner reachable, then d forces a step into s2, and the table propagates a path of True cells down-and-right to dp[5][5], which ends True. For the False example the reachable region never reaches the far corner.

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

Approach 4 — Space-optimized rolling row

The insight: row i needs only row i-1 (dp[i-1][j]) and the current row’s left neighbor (dp[i][j-1]). One 1-D array suffices if you carry the “from s1” contribution as the old value in place.

class Solution:
    def isInterleave(self, 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; without this guard the indexing math into s3 breaks.
• Greedy character picking — when both s1 and s2 offer the needed character you must consider both branches; committing to one greedily gives wrong Falses.
• The s3 index — the character being placed at state (i, j) is s3[i + j - 1], not s3[i] or s3[j].
• In the rolled version, forgetting to update dp[0] per row (the all-s1 boundary) breaks cases where a long s1 run leads the weave.

Pattern takeaway

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