LeetEye LeetEye
Medium 2D Dynamic Programming ~5 min

Interleaving String

2d-dp interleaving-string

Problem

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, such that:

- s = s1 + s2 + ... + sn
- t = t1 + t2 + ... + tm
- |n - m| <= 1
- The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Examples

Example 1
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
One way: aa + dbbc + bc + a + c
Example 2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Key Insight

dp[i][j] = can first i chars of s1 and first j chars of s2 form first i+j chars of s3?

dp[i][j] = can s1[0:i] and s2[0:j] interleave to form s3[0:i+j]? Transition: next char in s3 comes from s1 or s2.

How to Approach This Problem

Pattern Recognition: When you see keywords like interleaving string 2d-dp, think 2D Dynamic Programming.

Step-by-Step Reasoning

1 If len(s1) + len(s2) != len(s3):
Answer: Definitely impossible
Interleaving uses all characters from both strings exactly once.
2 dp[i][j] represents:
Answer: Whether s1[0:i] and s2[0:j] can interleave to form s3[0:i+j]
Boolean - can we form s3[0:i+j] using exactly i chars from s1 and j chars from s2.
3 dp[i][j] is True if:
Answer: Either A or B
s3[i+j-1] came from either s1[i-1] or s2[j-1]. Either path works.
4 dp[0][0] should be:
Answer: True
Empty strings interleave to form empty string.
5 dp[0][j] is True if:
Answer: s2[0:j] == s3[0:j]
Using 0 chars from s1, j chars from s2 must exactly match s3[0:j].

Solution

def isInterleave(s1: str, s2: str, s3: str) -> bool:
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False
    
    # Space-optimized 1D DP
    dp = [False] * (n + 1)
    
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 and j == 0:
                dp[j] = True
            elif i == 0:
                dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]
            elif j == 0:
                dp[j] = dp[j] and s1[i - 1] == s3[i - 1]
            else:
                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]

Complexity Analysis

Time O(m × n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice 2D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye