Interleaving String: 2D DP on Two Strings

You are given three strings s1, s2, and s3. Determine whether s3 is formed by an interleaving of s1 and s2. An interleaving means you weave the characters of s1 and s2 together, choosing the next character from either string at each step, while preserving the left-to-right order within each source string.

This is LeetCode 97: Interleaving String, and it is a clean example of 2D boolean DP on two strings. If you have worked through Edit Distance or Longest Common Subsequence, you already know the grid structure. The difference here is that each cell stores True or False instead of a numeric cost, and the transitions come from two directions (above and left) instead of three.

Why this problem matters

Interleaving String is a great problem for building fluency with 2D DP on two strings. Unlike Edit Distance, where you minimize a cost, or LCS, where you maximize a length, this problem asks a yes/no reachability question. The cell dp[i][j] answers: "Can I form the first i + j characters of s3 using exactly the first i characters of s1 and the first j characters of s2?"

That boolean framing changes how you think about transitions. You are not picking a minimum or maximum. You are checking whether at least one valid predecessor exists. This is a useful mental shift, because many DP problems in interviews use boolean reachability rather than optimization.

The brute force idea

Try every possible way to split s3 into characters from s1 and s2. At position k in s3, if s3[k] matches the current character in s1, try taking it from s1. If it matches the current character in s2, try taking it from s2. If neither matches, backtrack.

def is_interleave_recursive(s1, s2, s3, i, j, k):
    if k == len(s3):
        return i == len(s1) and j == len(s2)
    result = False
    if i < len(s1) and s1[i] == s3[k]:
        result = is_interleave_recursive(s1, s2, s3, i + 1, j, k + 1)
    if not result and j < len(s2) and s2[j] == s3[k]:
        result = is_interleave_recursive(s1, s2, s3, i, j + 1, k + 1)
    return result

This is exponential because the same (i, j) pair (note that k = i + j always) gets revisited many times. You need memoization, or better, a bottom-up table.

Building the 2D DP table

Define dp[i][j] as True if s1[:i] and s2[:j] can interleave to form s3[:i+j]. The table has (m + 1) rows and (n + 1) columns, where m = len(s1) and n = len(s2).

The recurrence checks two predecessors:

1. From above (dp[i-1][j]): if dp[i-1][j] is True and s1[i-1] == s3[i+j-1], then taking the next character from s1 extends a valid interleaving. Set dp[i][j] = True.
2. From the left (dp[i][j-1]): if dp[i][j-1] is True and s2[j-1] == s3[i+j-1], then taking the next character from s2 extends a valid interleaving. Set dp[i][j] = True.

If neither condition holds, dp[i][j] = False.

Base cases:

• dp[0][0] = True. Two empty strings interleave to form an empty string.
• First row dp[0][j]: only s2 contributes. dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1].
• First column dp[i][0]: only s1 contributes. dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1].

Before filling the table, check the length constraint: if len(s1) + len(s2) != len(s3), return False immediately. The lengths must add up.

Let's trace through s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac":

The answer is dp[5][5] = True. You can form s3 by interleaving s1 and s2.

def is_interleave(s1, s2, s3):
    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(1, m + 1):
        dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]

    for j in range(1, n + 1):
        dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = (
                (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])
            )

    return dp[m][n]

Time: O(m * n). Every cell in the 2D table gets filled exactly once.

Space: O(m * n). The full table.

Understanding the two transitions visually

Each cell dp[i][j] depends on at most two neighbors:

• Above dp[i-1][j]: you took the next character from s1. This means s1[i-1] must match s3[i+j-1]. Moving down a row in the table means consuming one character from s1.
• Left dp[i][j-1]: you took the next character from s2. This means s2[j-1] must match s3[i+j-1]. Moving right a column means consuming one character from s2.

There is no diagonal transition here. In Edit Distance and LCS, the diagonal represents "both strings advance." In interleaving, you take from exactly one string at each step, so the cell depends only on the cell above or the cell to the left.

Think of it as a path through the grid from (0, 0) to (m, n). Each step goes either down (take from s1) or right (take from s2). A valid interleaving corresponds to a path where every step matches the next character of s3.

Optimizing space to O(n)

Each row of the table only depends on the current row (left neighbor) and the row above it (above neighbor). You can drop the 2D grid down to a single 1D array and update it in place.

def is_interleave(s1, s2, s3):
    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):
        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):
            dp[j] = (
                (dp[j] and s1[i - 1] == s3[i + j - 1])
                or (dp[j - 1] and s2[j - 1] == s3[i + j - 1])
            )

    return dp[n]

Time: O(m * n). Same.

Space: O(n). One row of length n + 1.

In the space-optimized version, dp[j] before the update holds the value from the previous row (the "above" neighbor), and dp[j-1] holds the already-updated value from the current row (the "left" neighbor). This works because you iterate left to right, so by the time you need dp[j-1], it has already been updated for the current row.

Complexity analysis

Where m = length of s1, n = length of s2.

Edge cases to watch for

• Length mismatch: if len(s1) + len(s2) != len(s3), return False immediately. This is the most important early check.
• Both strings empty: s1 = "", s2 = "", s3 = "". Return True. The base case dp[0][0] = True handles this.
• One string empty: if s1 is empty, check whether s2 == s3. If s2 is empty, check whether s1 == s3. The first row or first column of the table handles this naturally.
• No valid interleaving: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc". The characters are all present, but the ordering does not work. dp[m][n] will be False.
• Identical characters in both strings: e.g., s1 = "aa", s2 = "aa", s3 = "aaaa". Multiple valid interleavings exist, but you only need to find one. The DP table will have many True cells.

The building blocks

This problem is built on 2D string DP and character matching from two sources. The structure is:

• State: dp[i][j] = can s1[:i] and s2[:j] form s3[:i+j]?
• Transition: check above (take from s1) or left (take from s2), each gated by a character match against s3[i+j-1]
• Base case: dp[0][0] = True, first row checks s2 against s3, first column checks s1 against s3

The 2D string DP building block is the same one that powers Edit Distance and Longest Common Subsequence. The table dimensions, the row-by-row fill order, and the space optimization technique are identical across these problems. What changes is the recurrence: LCS maximizes, Edit Distance minimizes, and Interleaving String checks boolean reachability.

The character matching from two sources building block is specific to this problem. At each step, you decide which of two input strings provides the next character. This two-source matching idea also appears in problems like merging sorted arrays and certain game-theory DP problems.

From understanding to recall

You now know how to set up the boolean 2D table, why each cell depends on its above and left neighbors, and how the space optimization works. But understanding the pattern once is not the same as producing it under pressure in an interview.

The tricky parts are: remembering that k = i + j eliminates the need for a third dimension, getting the base cases right for the first row and first column, and writing the boolean OR transition without confusing it with the min/max transitions from Edit Distance or LCS. Those details are exactly the kind of thing that slips away after a week.

The 2D string DP building block is one of roughly 60 reusable patterns in the CodeBricks system. You drill each block individually with spaced repetition until writing the solution from scratch is automatic. Interleaving String, Edit Distance, and LCS together form the core of the two-string DP family. Locking all three in early means you can handle any variant that shows up in an interview.

Related posts

• Edit Distance - The classic 2D string DP problem that minimizes edit cost instead of checking boolean reachability
• Longest Common Subsequence - The foundational two-string DP problem that maximizes shared subsequence length