Interleaving String: Three-String DP
The interleaving string problem asks a deceptively simple question: given three strings `s1`, `s2`, and `s3`, can you form `s3` by interleaving characters from `s1` and `s2` while preserving the...
Key Insights
- The interleaving string problem requires tracking positions in two source strings simultaneously, making it a natural fit for 2D dynamic programming where dp[i][j] represents whether prefixes of length i and j can form a prefix of length i+j in the target.
- Greedy approaches fail because when both source strings offer a matching character, you cannot determine locally which choice leads to a valid solution—you must explore both paths.
- Space optimization from O(m×n) to O(n) is possible because each cell only depends on the cell above it and the cell to its left, allowing you to reuse a single row.
Problem Introduction
The interleaving string problem asks a deceptively simple question: given three strings s1, s2, and s3, can you form s3 by interleaving characters from s1 and s2 while preserving the relative order of characters within each source string?
This is LeetCode problem 97, and it’s a classic example of why dynamic programming exists. The problem appears straightforward until you try to solve it.
# Problem Visualization
s1 = "aab"
s2 = "axy"
s3 = "aaxaby"
# One valid interleaving:
# s3 = a a x a b y
# ↑ ↑ ↑ from s1 (a, a, b)
# ↑ ↑ ↑ from s2 (a, x, y)
# The key constraint: characters from s1 must appear in order (a before a before b)
# and characters from s2 must appear in order (a before x before y)
The first observation is critical: if len(s3) != len(s1) + len(s2), the answer is immediately False. Every character must be used exactly once.
Why Greedy Fails
Your first instinct might be to process s3 character by character, greedily taking from whichever source string matches. This fails spectacularly.
def interleave_greedy(s1: str, s2: str, s3: str) -> bool:
"""This approach DOES NOT WORK. Don't use it."""
if len(s1) + len(s2) != len(s3):
return False
i, j = 0, 0 # pointers for s1 and s2
for char in s3:
if i < len(s1) and s1[i] == char:
i += 1
elif j < len(s2) and s2[j] == char:
j += 1
else:
return False
return True
# Counterexample:
s1 = "aab"
s2 = "aac"
s3 = "aaabac"
# Greedy processing of s3:
# 'a' -> matches s1[0], take from s1, i=1
# 'a' -> matches s1[1], take from s1, i=2
# 'a' -> matches s2[0], take from s2, j=1
# 'b' -> matches s1[2], take from s1, i=3
# 'a' -> matches s2[1], take from s2, j=2
# 'c' -> matches s2[2], take from s2, j=3
# Result: True (happens to work)
# But consider s3 = "aacaab":
# 'a' -> matches s1[0], take from s1, i=1
# 'a' -> matches s1[1], take from s1, i=2
# 'c' -> doesn't match s1[2]='b', try s2[0]='a'... FAIL
# Greedy returns False, but valid interleaving exists!
# Correct: take s2[0], s2[1], s2[2], then s1[0], s1[1], s1[2]
The problem is that when both strings offer a matching character, the greedy choice might lead to a dead end while the other choice succeeds. You need to explore both possibilities.
Recursive Solution with Memoization
Let’s build intuition with a top-down recursive approach. The key insight is that we only need to track positions i and j in s1 and s2—the position in s3 is always i + j.
from functools import cache
def is_interleave_memo(s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3):
return False
@cache
def dp(i: int, j: int) -> bool:
"""Can s1[i:] and s2[j:] interleave to form s3[i+j:]?"""
k = i + j
# Base case: consumed all characters
if i == len(s1) and j == len(s2):
return True
# Try taking from s1
if i < len(s1) and s1[i] == s3[k]:
if dp(i + 1, j):
return True
# Try taking from s2
if j < len(s2) and s2[j] == s3[k]:
if dp(i, j + 1):
return True
return False
return dp(0, 0)
At each state (i, j), we’re asking: “Can the remaining portions of s1 and s2 form the remaining portion of s3?” We have at most two choices—take from s1 if it matches, or take from s2 if it matches. The memoization ensures we never recompute the same subproblem.
The state space is O(m × n) where m = len(s1) and n = len(s2), and each state takes O(1) to compute (after subproblems are cached).
2D Dynamic Programming Table
Converting to bottom-up DP makes the solution more explicit and often faster in practice due to better cache locality.
Define dp[i][j] as: “Can s1[0:i] and s2[0:j] interleave to form s3[0:i+j]?”
def is_interleave_2d(s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
# dp[i][j] = can s1[0:i] and s2[0:j] form s3[0:i+j]?
dp = [[False] * (n + 1) for _ in range(m + 1)]
# Base case: empty strings form empty string
dp[0][0] = True
# Fill first row: using only s2
for j in range(1, n + 1):
dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
# Fill first column: using only s1
for i in range(1, m + 1):
dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
# Fill the rest of the table
for i in range(1, m + 1):
for j in range(1, n + 1):
k = i + j - 1 # current position in s3
# Option 1: last character came from s1
from_s1 = dp[i-1][j] and s1[i-1] == s3[k]
# Option 2: last character came from s2
from_s2 = dp[i][j-1] and s2[j-1] == s3[k]
dp[i][j] = from_s1 or from_s2
return dp[m][n]
Let’s trace through a small example to solidify understanding:
# s1 = "ab", s2 = "cd", s3 = "acbd"
#
# Building the DP table:
#
# "" c d
# +-----+-----+-----+
# "" | T | F | F | dp[0][1]: s3[0]='a' != s2[0]='c'
# +-----+-----+-----+
# a | T | T | F | dp[1][1]: s3[1]='c' == s2[0], and dp[1][0]=T
# +-----+-----+-----+
# b | F | T | T | dp[2][2]: s3[3]='d' == s2[1], and dp[2][1]=T
# +-----+-----+-----+
#
# Answer: dp[2][2] = True
Space Optimization to O(n)
Looking at the recurrence, dp[i][j] depends only on:
dp[i-1][j](cell directly above)dp[i][j-1](cell directly to the left)
This means we can use a single row and update it in place, as long as we process left to right.
def is_interleave_optimized(s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
# Optimization: use the shorter string for the DP array
if m < n:
s1, s2, m, n = s2, s1, n, m
# dp[j] represents dp[i][j] for current row i
dp = [False] * (n + 1)
# Initialize for i = 0 (using only s2)
dp[0] = True
for j in range(1, n + 1):
dp[j] = dp[j-1] and s2[j-1] == s3[j-1]
# Process each row
for i in range(1, m + 1):
# Update dp[0] for this row (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
# dp[j] currently holds dp[i-1][j] (from previous row)
# dp[j-1] holds dp[i][j-1] (already updated this row)
from_s1 = dp[j] and s1[i-1] == s3[k]
from_s2 = dp[j-1] and s2[j-1] == s3[k]
dp[j] = from_s1 or from_s2
return dp[n]
The trick of swapping s1 and s2 to ensure the shorter one is used for the array dimension is a common optimization. It reduces space from O(max(m,n)) to O(min(m,n)).
Complexity Analysis & Edge Cases
Time Complexity: O(m × n) for all approaches. We visit each state exactly once.
Space Complexity:
- Memoization: O(m × n) for the cache, plus O(m + n) recursion stack
- 2D DP: O(m × n)
- Optimized: O(min(m, n))
Edge Cases to Handle:
def is_interleave_robust(s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
# Edge case 1: Length mismatch
if m + n != len(s3):
return False
# Edge case 2: Both empty
if m == 0 and n == 0:
return len(s3) == 0
# Edge case 3: One string empty
if m == 0:
return s2 == s3
if n == 0:
return s1 == s3
# Edge case 4: All identical characters
# s1 = "aaa", s2 = "aaa", s3 = "aaaaaa"
# This works correctly with DP but can be slow with naive recursion
# ... rest of DP solution
The “all identical characters” case is particularly nasty for naive recursion without memoization—it creates an exponential number of paths. The DP approach handles it gracefully.
Related Problems & Extensions
The interleaving string problem belongs to a family of multi-string DP problems where you track positions across multiple inputs:
Edit Distance (LeetCode 72): Track positions in two strings, compute minimum operations to transform one into another. Similar 2D table structure.
Longest Common Subsequence (LeetCode 1143): Another two-string DP where dp[i][j] represents the LCS of prefixes. Same space optimization applies.
Scramble String (LeetCode 87): A harder variant where you can recursively swap substrings. Requires 3D DP or interval DP thinking.
Distinct Subsequences (LeetCode 115): Count how many ways s contains t as a subsequence. Same two-pointer state space.
The pattern to recognize: when a problem involves matching or combining multiple sequences while respecting order constraints, think about tracking positions in each sequence as your DP state. The state space is the product of sequence lengths, and transitions involve advancing one pointer at a time.
For interleaving specifically, the mental model is a grid where moving right means taking from s2, moving down means taking from s1, and you’re trying to find any path from top-left to bottom-right that spells out s3. Once you see it this way, the DP solution writes itself.