97. Interleaving String

MediumTwo-Dimensional Dynamic Programming2D boolean dynamic programming over string prefixesTwo-sequence interleaving DP

Interleaving String

Given strings s1, s2, and s3, determine whether s3 can be formed by interleaving s1 and s2. An interleaving keeps the relative order of characters within s1 and within s2 while merging them; every character of s1 and s2 must be used exactly once.

Open official problem prompt ↗

In plain English

Decide if the target string is an order-preserving merge of the two source strings, using each source character exactly once.

Picture it like this

Two dealers each hold a fixed stack of cards. You build one output pile by repeatedly taking the top card from either stack. The question is whether some sequence of choices reproduces the target pile exactly.

Example

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Why: s3 can be split as (aa)(dbbc)(bc)(a)(c) alternating between s1's aabcc and s2's dbbca while preserving each string's order.

Constraints

0 <= s1.length, s2.length <= 1000 <= s3.length <= 200s1, s2, and s3 consist of lowercase English letters

Pattern lesson

See the pattern, then code

Two-sequence interleaving DP

↗

Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. Whether the first i chars of s1 and first j chars of s2 can build the first i+j chars of s3 depends only on which string supplied the last character. That last character matched either s1[i-1] or s2[j-1], reducing to a smaller sub-state.

New words, made simpleKnow these before the algorithm

Interleaving: A merge of two sequences that keeps the relative order inside each
Prefix state: dp[i][j]: can the first i chars of s1 plus first j chars of s2 form the first i+j chars of s3
Diagonal coupling: The position in s3 is always i+j, so the two pointers advance together

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute-force recursion

Explores overlapping (i,j) states repeatedly; blows up exponentially.

At each step try consuming the next char from s1 or from s2 whenever it matches s3, recursing on both.

Time O(2^(m+n))Space O(m+n)

Best choice2D prefix DP

Every (i,j) pair is evaluated once; can be reduced to O(n) space with a rolling row.

Fill a boolean table where each cell depends on the cell above or to the left, gated by a character match.

Time O(m*n)Space O(m*n)

The rule we keep true

Invariant

dp[i][j] is true exactly when s3[:i+j] is a valid interleaving of s1[:i] and s2[:j]; the most recently consumed character of s3 is at index i+j-1.

Why this is correct

Reasoning

The last character of s3[:i+j] came from either s1 or s2. If it came from s1 it must equal s1[i-1] and the remainder must interleave (dp[i-1][j]); symmetrically for s2. Covering both cases is exhaustive, so the recurrence captures every valid merge.

The algorithm in three movesSay these aloud before coding

1Reject immediately if len(s1) + len(s2) != len(s3)

len check: 5 + 5 == 10 ok

2Let dp[i][j] mean s1[:i] and s2[:j] interleave to s3[:i+j]

dp[0][j] follows s2 prefix, dp[i][0] follows s1 prefix

3dp[i][j] is true if s1's last char matches and dp[i-1][j], or s2's last char matches and dp[i][j-1]

dp[5][5] = true

4Seed dp[0][0] = true and read off dp[m][n]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read|s1|=5, |s2|=5, |s3|=10

2 · AskCan lengths even match?

3 · Update state5 + 5 == 10

4 · ResultPasses, continue

Key takeaway

The target s3; highlighted positions show characters contributed by s1 during one valid interleaving.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4-5Length sanity check
If the combined lengths differ, no interleaving can exist; return early.
2
Lines 6-7Table and base case
dp is (m+1)x(n+1); the empty/empty state is true.
3
Lines 8-14Fill by matches
Each cell becomes true if a matching char extends a true neighbor from s1 (above) or s2 (left).
4
Lines 15Answer
dp[m][n] tells whether the whole target is an interleaving.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Any string empty: if s1 is empty the answer is s2 == s3
All three empty returns true
Correct rejection when the length sum mismatches even if characters look compatible

Common beginner mistakes

Using a greedy match that commits to one source too early; a character may be available in both and only DP explores both
Indexing s3 with the wrong offset (it must be i+j-1, not i-1 or j-1)
Forgetting to initialize the first row and first column border states

Check your understanding

Why is a greedy left-to-right match insufficient when the next needed character appears in both s1 and s2?

PyPython 3 · solution.py

Optimal

1class Solution:2    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:3        m, n = len(s1), len(s2)4        if m + n != len(s3):5            return False6        dp = [[False] * (n + 1) for _ in range(m + 1)]7        dp[0][0] = True8        for i in range(m + 1):9            for j in range(n + 1):10                if i > 0 and s1[i - 1] == s3[i + j - 1]:11                    dp[i][j] = dp[i][j] or dp[i - 1][j]12                if j > 0 and s2[j - 1] == s3[i + j - 1]:13                    dp[i][j] = dp[i][j] or dp[i][j - 1]14        return dp[m][n]

Time complexityO(m*n)Optimized

Space complexityO(m*n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftBloomberg

Interleaving String

Interleaving String

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two-Dimensional Dynamic Programming