Interleaving String

Difficulty: Medium Source: NeetCode

Problem

Given strings s1, s2, and s3, return true if s3 is formed by an interleaving of s1 and s2. An interleaving of two strings keeps the relative order of characters from each string but merges them together.

Example 1: Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true

Example 2: Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false

Example 3: Input: s1 = "", s2 = "", s3 = "" Output: true

Constraints:

• 0 <= s1.length, s2.length <= 100
• s3.length == s1.length + s2.length

Prerequisites

Before attempting this problem, you should be comfortable with:

• 2D DP on two strings — the same table structure as LCS
• Recursion with two pointers — advancing through two source strings simultaneously

1. Brute Force / Recursive

Intuition

Use two pointers i and j tracking how far we’ve consumed s1 and s2. The current character of s3 is s3[i+j]. At each step, we try matching it with s1[i] (advance i) or s2[j] (advance j). We succeed if we consume all of s1 and s2 simultaneously.

Algorithm

1. Define dfs(i, j) = can s1[:i] and s2[:j] interleave to form s3[:i+j]?
2. Base case: i == len(s1) and j == len(s2) → return True.
3. If i < len(s1) and s1[i] == s3[i+j], try dfs(i+1, j).
4. If j < len(s2) and s2[j] == s3[i+j], try dfs(i, j+1).
5. Return True if any path succeeds.

Solution

def isInterleave(s1, s2, s3):
    if len(s1) + len(s2) != len(s3):
        return False

    def dfs(i, j):
        if i == len(s1) and j == len(s2):
            return True
        if i < len(s1) and s1[i] == s3[i + j]:
            if dfs(i + 1, j):
                return True
        if j < len(s2) and s2[j] == s3[i + j]:
            if dfs(i, j + 1):
                return True
        return False

    return dfs(0, 0)


print(isInterleave("aabcc", "dbbca", "aadbbcbcac"))  # True
print(isInterleave("aabcc", "dbbca", "aadbbbaccc"))  # False
print(isInterleave("", "", ""))                       # True

Complexity

• Time: O(2^(m+n)) — exponential without memoization
• Space: O(m+n) — recursion depth

2. Bottom-Up DP (Tabulation)

Intuition

Build a (m+1) x (n+1) boolean table where dp[i][j] is True if s1[:i] and s2[:j] can interleave to form s3[:i+j]. Start with dp[0][0] = True. Fill the first row using only s2 characters, and the first column using only s1 characters. For interior cells, it’s true if we can come from the left (match s2[j-1]) or from above (match s1[i-1]).

Algorithm

1. If len(s1) + len(s2) != len(s3), return False.
2. Create (m+1) x (n+1) dp table, dp[0][0] = True.
3. Fill first column: dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1].
4. Fill first row: dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1].
5. Interior: 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]).
6. Return dp[m][n].

Solution

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

    return dp[m][n]


print(isInterleave("aabcc", "dbbca", "aadbbcbcac"))  # True
print(isInterleave("aabcc", "dbbca", "aadbbbaccc"))  # False
print(isInterleave("", "", ""))                       # True
print(isInterleave("a", "b", "ab"))                  # True
print(isInterleave("a", "b", "ba"))                  # True

Complexity

• Time: O(m * n)
• Space: O(m * n) — reducible to O(n) with a rolling row

Common Pitfalls

Forgetting the length check. If len(s1) + len(s2) != len(s3), it’s immediately impossible. Don’t skip this — it prevents index-out-of-bounds errors too.

Wrong index into s3. The character we’re matching in s3 at position (i, j) is s3[i+j-1] (1-indexed i, j). Getting this formula wrong is the most common bug in this problem.

Greedy won’t work. You might think “just scan left to right and match whichever string fits” — but that fails on ambiguous characters. For example if s1 = "aa" and s2 = "aa", a greedy approach can’t know which string to draw from. DP is necessary.