97 - Interleaving String

Difficulty: Medium | Pattern: Dynamic Programming (2D) | Company tags: Amazon, Google, Microsoft

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

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

Example 1:

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

Example 2:

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

Constraint: 0 <= s1.length, s2.length <= 100

Approach: 2D DP — O(m×n), O(m×n)

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

Transition:

• dp[i][j] is True if:
  • dp[i-1][j] is True AND s1[i-1] == s3[i+j-1] (use next char from s1), OR
  • dp[i][j-1] is True AND s2[j-1] == s3[i+j-1] (use next char from s2)

def isInterleave(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
    
    # Base case: only using s1
    for i in range(1, m + 1):
        dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
    
    # Base case: only using s2
    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]

Algorithm Flow

Dry Run

s1 = "ab", s2 = "bc", s3 = "abbc" (m=2, n=2)

	""	b	c
""	T	T(b=b)	F
a	T(a=a)	dp[1][1]: a=b? F, b=b? T → T	dp[1][2]: dp[0][2]=F,dp[1][1]=T,s2[1]=c=s3[3]=c → T
b	dp[2][0]: dp[1][0]=T,s1[1]=b=s3[2]=b → T	dp[2][1]: dp[1][1]=T,b=b → T	dp[2][2]: dp[1][2]=T,s1[1]=b=s3[3]=c? F; dp[2][1]=T,s2[1]=c=s3[3]=c → T

dp[2][2] = True ✓

Space-Optimized: O(n) Space

def isInterleave(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 j in range(n + 1):
        dp[j] = dp[j-1] and s2[j-1] == s3[j-1] if j > 0 else True
    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]

Edge Cases

• len(s1) + len(s2) != len(s3) → immediately False
• Either string empty → check if the other equals s3
• Strings with repeated characters → DP handles correctly via indices

Complexity

Approach	Time	Space
2D DP	O(m×n)	O(m×n)
1D DP	O(m×n)	O(n)

Key Terms

Term	Definition
Interleaving	Merging two sequences while preserving the relative order of characters within each.
2D DP table	dp[i][j] tracks whether a prefix of s3 can be formed from prefixes of s1 and s2 of lengths i and j.
State transition	Rule for deriving dp[i][j] from dp[i-1][j] and dp[i][j-1].
Rolling array	Space optimization that keeps only the previous DP row, reducing space from O(m×n) to O(n).
Prefix length invariant	i + j characters of s3 must always match the combined length of the consumed prefixes.

FAQ

1. Can this be solved without extra space? Not fully — the 1D rolling-array version still needs O(n) space; true O(1) space isn't practical because the transition depends on the previous row.
2. What if s1 or s2 is empty? The DP degenerates to a single base-case row/column check: s3 must equal the non-empty string exactly.
3. How would this change if characters could be reused across s1 and s2? It would no longer be interleaving; the problem would become a subsequence/coverage problem requiring a different formulation.
4. Why check len(s1) + len(s2) != len(s3) upfront? It's an O(1) short-circuit — if lengths don't match, no interleaving is possible, avoiding wasted DP computation.
5. Can this be solved recursively with memoization instead of iterative DP? Yes — top-down recursion on (i, j) with memoization is equivalent and often easier to reason about, though iterative DP avoids recursion overhead.

Quick Revision

• Problem: determine if s3 can be formed by interleaving s1 and s2 while preserving each string's internal order.
• First check: len(s1) + len(s2) == len(s3), else return False immediately.
• dp[i][j] = True if s3[:i+j] is an interleaving of s1[:i] and s2[:j].
• Transition: come from dp[i-1][j] (matched via s1) or dp[i][j-1] (matched via s2).
• Base row/column initialized by matching a single string against a prefix of s3.
• Answer is dp[m][n].
• Time O(m×n), space O(m×n), optimizable to O(n) with a rolling 1D array.
• Pattern generalizes to "can sequence A be built from two other sequences" DP problems.

Related Problems

• 72 - Edit Distance
• 115 - Distinct Subsequences
• 10 - Regular Expression Matching