Interleaving String — 2D DP for String Validity Checking

Problem Statement#

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2. An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, and then they are alternated. The strings s1, s2, and s3 must all be used in full.

Constraints:

• 0 <= s1.length, s2.length <= 100
• s3.length == s1.length + s2.length
• s1, s2, and s3 consist of lowercase English letters

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

Why This Problem Matters#

Interleaving String is the Boolean variant of 2D sequence DP — instead of computing a count or minimum, you determine whether a valid configuration exists. This Boolean structure appears frequently in parsing, grammar checking, and string validation problems.

Google and Amazon include this problem to test 2D DP state design when the objective is existence (true/false) rather than optimization. The DP recurrence and table structure are nearly identical to LCS and Edit Distance, but the fill logic is boolean OR instead of arithmetic min/max.

The key interview skill this tests: correctly defining dp[i][j] so that it captures exactly the right subproblem — "can we match exactly i characters of s1 and j characters of s2 to form s3[0..i+j-1]?"

The Core Insight#

State definition: dp[i][j] = True if s3[:i+j] can be formed by interleaving s1[:i] and s2[:j].

Key observation: At position i+j in s3, the last character came from either s1[i-1] or s2[j-1].

Recurrence:

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])

• If the last character came from s1: the preceding state is dp[i-1][j] (used i-1 chars from s1 and j chars from s2), and s1[i-1] must match s3[i+j-1].
• If the last character came from s2: the preceding state is dp[i][j-1], and s2[j-1] must match s3[i+j-1].

Base cases:

• dp[0][0] = True — empty strings form an empty interleaving.
• dp[i][0]: s3 formed only from s1 prefix — dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1].
• dp[0][j]: s3 formed only from s2 prefix — dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1].

Answer: dp[len(s1)][len(s2)]

Length check first: If len(s1) + len(s2) != len(s3), return False immediately.

Building the DP Solution#

Step 1 — Memoized recursion:

from functools import lru_cache
 
def isInterleave(s1, s2, s3):
    if len(s1) + len(s2) != len(s3):
        return False
    @lru_cache(None)
    def dp(i, j):
        if i == 0 and j == 0:
            return True
        k = i + j - 1  # current index in s3
        result = False
        if i > 0 and s1[i-1] == s3[k]:
            result = result or dp(i-1, j)
        if j > 0 and s2[j-1] == s3[k]:
            result = result or dp(i, j-1)
        return result
    return dp(len(s1), len(s2))

Step 2 — Bottom-up 2D:

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):
            k = i + j - 1
            dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[k]) or \
                        (dp[i][j-1] and s2[j-1] == s3[k])
    return dp[m][n]

Visual Dry Run#

Input: s1 = "aab", s2 = "bc", s3 = "aabbc"

• dp[0][0] = T
• dp[1][0]: s1[0]='a'==s3[0]='a' and dp[0][0]=T → T
• dp[2][0]: s1[1]='a'==s3[1]='a' and dp[1][0]=T → T
• dp[3][0]: s1[2]='b'==s3[2]='a'? No → F
• dp[0][1]: s2[0]='b'==s3[0]='a'? No → F
• dp[2][1]: (dp[1][1]=F and s1='a'==s3[2]='b'? No) or (dp[2][0]=T and s2='b'==s3[2]='b'? Yes) → T
• dp[3][2]: (dp[2][2] and s1[2]='b'==s3[4]='c'? No) or (dp[3][1] and s2[1]='c'==s3[4]='c'? T and T) → T

Optimized Solution#

Python#

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
 
        # Quick length check — necessary condition
        if m + n != len(s3):
            return False
 
        # 1D rolling DP: dp[j] = can we form s3[:i+j] using s1[:i] and s2[:j]
        dp = [False] * (n + 1)
        dp[0] = True
 
        # Initialize first row (using only s2)
        for j in range(1, n + 1):
            dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]
 
        # Fill row by row
        for i in range(1, m + 1):
            # First column: using only s1
            dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
 
            for j in range(1, n + 1):
                k = i + j - 1  # current index in s3
                dp[j] = (dp[j] and s1[i - 1] == s3[k]) or \
                         (dp[j - 1] and s2[j - 1] == s3[k])
 
        return dp[n]

JavaScript#

var isInterleave = function(s1, s2, s3) {
    const m = s1.length, n = s2.length;
 
    if (m + n !== s3.length) return false;
 
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
 
    for (let j = 1; j <= n; j++) {
        dp[j] = dp[j - 1] && s2[j - 1] === s3[j - 1];
    }
 
    for (let i = 1; i <= m; i++) {
        dp[0] = dp[0] && s1[i - 1] === s3[i - 1];
 
        for (let j = 1; j <= n; j++) {
            const k = i + j - 1;
            dp[j] = (dp[j] && s1[i - 1] === s3[k]) ||
                    (dp[j - 1] && s2[j - 1] === s3[k]);
        }
    }
 
    return dp[n];
};

Complexity Analysis#

Common Mistakes#

1. Forgetting the length check. If len(s1) + len(s2) != len(s3), the answer is always False. Skipping this check wastes time and may cause index-out-of-bounds errors when computing s3[i+j-1].

2. Incorrect index into s3. The index into s3 at state (i, j) is i + j - 1 (0-indexed). Using i + j instead reads one position too far and produces wrong results, especially silently for short strings.

3. Using or when a True was already found. In the 1D rolling array approach, dp[j] in the new row can be True from either the s1 or s2 direction — use or correctly. Overwriting with and would incorrectly require both to be true.

4. Not separately initializing the first row and column. The first row (dp[0][j]) uses only characters from s2. The first column (dp[i][0]) uses only characters from s1. These must be initialized separately before filling the interior.

5. Off-by-one in base case. dp[0][0] = True represents matching both empty prefixes against the empty s3. Any initialization of dp[0][0] to False immediately makes the entire table False.

Interview Tips#

• Start with the length check — it's the first thing to say and shows you understand the problem constraints.
• State the DP semantics precisely: "dp[i][j] is True if we can form s3[:i+j] using exactly i chars from s1 and j chars from s2, in order."
• Draw a small table (3x3 or 4x4) and fill it while explaining the recurrence — Boolean DP is cleaner to trace than arithmetic DP.
• Compare to LCS: "The structure is identical to LCS — same 2D table, same diagonal/up/left transitions — but instead of max, we use boolean OR."
• For the follow-up "can you reduce space?": "Yes — I only need the previous row (from above) and the current value to the left, so a 1D rolling array suffices."

Follow-up Questions#

Q: What if s3 can be formed by interleaving more than 2 strings? Extend to 3D DP: dp[i][j][k] = whether s4[:i+j+k] can be formed from s1[:i], s2[:j], s3[:k]. O(mnp) time and space.

Q: Can BFS solve this problem? Yes — treat (i, j) as a state (how many characters consumed from s1 and s2). BFS from (0, 0) to (m, n), moving right (use s2 char) or down (use s1 char) when the corresponding s3 character matches. Both BFS and DP are O(m*n).

Q: What if characters in s1 and s2 can be reused? The problem fundamentally changes — each s3 character can be matched from multiple sources. This becomes a different type of matching problem, not a standard 2D DP.

Q: How do you trace back which characters came from which string? Store a parent[i][j] table recording whether the last character came from s1 (moved down) or s2 (moved right). Backtrack from (m, n) to (0, 0) to reconstruct the interleaving.

Key Takeaways#

• dp[i][j] = True if s3[:i+j] can be formed by interleaving s1[:i] and s2[:j].
• The recurrence: 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]).
• Always check len(s1) + len(s2) == len(s3) first.
• The s3 index at cell (i, j) is always i + j - 1 (1-indexed i, j) — never forget the -1.
• This is Boolean 2D DP: use or instead of arithmetic operations, but the table structure and rolling-array optimization are identical to LCS and Edit Distance.
• Google and Amazon use this problem to test whether candidates can adapt familiar 2D DP patterns to Boolean objectives.