Difficulty: Medium2-D Dynamic Programming

Interleaving String

Problem in Plain English

Given two source strings and a target, decide whether the target can be formed by merging the sources character by character while keeping the internal order of each source intact.

Problem Statement

Given strings s1, s2, and s3, return true if s3 is formed by an interleaving of s1 and s2, and false otherwise. An interleaving merges the two sources character by character so that every character of s3 comes from exactly one source.

Each source keeps its internal order: reading only the characters taken from s1 must replay s1, and likewise for s2. When both sources offer the same next character, either choice may lead onward, so both paths must be explored.

If the lengths do not add up (len(s1) + len(s2) differs from len(s3)), the answer is immediately false.

Constraints

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

Examples

Example 1

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

One valid merge is aa from s1, dbbc from s2, bc from s1, a from s2, then c from s1. Joining those pieces yields aadbbcbcac and reading either source alone preserves its original order. Other valid choices can exist.

Example 2

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

After the forced aa from s1 and d from s2, the target demands three b characters. There is only one b left in s1 and two in s2, so all three must be consumed. The next target character is a, but both sources now offer c; the remaining a in s2 is blocked behind its c. Equal lengths and character counts therefore do not guarantee interleaving.

Example 3

Input: s1 = "", s2 = "", s3 = ""
Output: true

No characters need to be consumed. Starting at the empty prefix already consumes the whole empty target, so the answer is true.

Example 4

Input: s1 = "a", s2 = "ab", s3 = "aba"
Output: true

Taking the first a from s1 strands the next b because s2 still starts with a. Taking ab from s2 first, then a from s1, succeeds. This is a small counterexample to always choosing s1 on a tie.

Intuition

After taking i characters from s1 and j from s2, exactly i + j target characters have been consumed. The next character must match the next unused character of at least one source. In Example 1 the first two a characters must come from s1, then d must come from s2. Later both sources offer b, so one matching choice is not enough: remember both possibilities. A pair of consumed lengths completely describes the remaining problem; the detailed history does not matter.

Approaches

Recursive Branching

Solution Details

Reveal Recursive Branching: intuition, complexity, and code

Intuition

Try each source that can supply the next target character, backtracking when the remaining suffix cannot be formed. State (i, j) means the first i characters of s1 and j characters of s2 are already used; target position is i + j. In Example 1 the forced aa, then d, lead to a b that either source can supply. Recursion tries s1 first and only tries s2 if that path fails.

Step-by-Step Logic

Reject unequal total lengths before starting; Example 1 has 5 + 5 = 10, so call dfs(0, 0). Use indices instead of creating suffix strings.
At each state compute k = i + j. If k equals the target length, return true; otherwise try s1[i] when in bounds and equal to s3[k]. The first two calls consume aa from s1, reaching (2, 0).
If the s1 continuation fails or cannot start, try s2[j] under the same matching rule. At (2, 0), only d from s2 fits, reaching (2, 1).
When both sources fit, retain the second choice for backtracking rather than discarding it. At (4, 3), taking c from s1 reaches (5, 3), where neither source can supply the next a; retry c from s2 instead.
Propagate true immediately on the first successful continuation. The successful suffix visits (4, 4), (4, 5), and (5, 5), so Example 1 returns true. If all matching children fail, return false.

Why It Works

At state (i, j), every legal continuation must take its next character from s1[i] or s2[j], because skipping would discard a required source character and reordering is forbidden. The search explores every matching choice until a successful continuation is found. Each call consumes one source character, so it reaches either a mismatch or the base case. After the length guard, reaching the target end means both sources are exhausted. By induction on the number of remaining characters, the base case is valid and a state returns true exactly when at least one legal child can finish.

Dry Run

Recursive Branching: variable states at each step
i	j	s3[i+j]	Candidates at entry (calls in preorder)	Returned result after children
0	0	a	s1 matches; s2 blocked	true via (1,0); s2 not tried
1	0	a	s1 matches; s2 blocked	true via (2,0); s2 not tried
2	0	d	s1 blocked; s2 matches	true via (2,1)
2	1	b	s1 matches; s2 matches	true via (3,1); s2 not tried
3	1	b	s1 blocked; s2 matches	true via (3,2)
3	2	c	s1 matches; s2 blocked	true via (4,2); s2 not tried
4	2	b	s1 blocked; s2 matches	true via (4,3)
4	3	c	s1 matches; s2 matches	true via (4,4); s1 child false
5	3	a	s1 blocked; s2 blocked	false; no successful child
4	4	a	s1 blocked; s2 matches	true via (4,5)
4	5	c	s1 matches; s2 blocked	true via (5,5); s2 not tried
5	5	end	both consumed	true

Complexity Analysis

Time Complexity

O(2^{m+n})

Space Complexity

O(m+n+1)

Let m and n be source lengths. The length check is constant work and allocates no search storage on mismatch. Each recursive node does constant work and has at most two children, giving an exponential upper bound; repeated (i, j) states are not cached. At most m + n + 1 frames are live, including the all-empty case. Inputs are referenced without slicing. Short-circuit success makes many valid cases fast, but ambiguous late failures remain infeasible at length 100 + 100; use the grid for unrestricted maximum inputs.

Code

Solution.java

1class Solution {2    public boolean isInterleave(String s1, String s2, String s3) {3        if (s1.length() + s2.length() != s3.length()) return false;4        return dfs(s1, s2, s3, 0, 0);5    }6
7    private boolean dfs(String s1, String s2, String s3, int i, int j) {8        // Consuming i and j source characters fixes the target index.9        int k = i + j;10        if (k == s3.length()) return true;11        if (i < s1.length() && s1.charAt(i) == s3.charAt(k)12            && dfs(s1, s2, s3, i + 1, j)) return true;13        // A matching first choice may fail later; preserve the alternative.14        return j < s2.length() && s2.charAt(j) == s3.charAt(k)15            && dfs(s1, s2, s3, i, j + 1);16    }17}

Hints

Hint 1

Compare total lengths first: a mismatch between len(s1) + len(s2) and len(s3) ends the problem at once.

Hint 2

At state (i, j) the only relevant target character is s3[i + j], taken from s1[i] or s2[j] when equal.

Hint 3

Record reachable prefix pairs in a grid so a state reached twice is reused instead of re-searched.

Edge Cases

All three strings empty, which interleaves trivially to true.
One source empty while the other equals the target exactly, such as s1 = "", s2 = "ab", s3 = "ab".
Equal total lengths with no valid merge, such as the second example ending in false.
Equal character counts can still fail because order matters: Example 2 has the same counts as the two sources combined.
When both next characters match, the source choice may need to be undone; a, ab, aba is true only after choosing s2 first.
An empty source requires the other source to equal the entire target, not merely share its character counts.

Common Mistakes and Interview Tips

Choosing greedily when both sources match: the wrong pick strands the merge while the other pick completes it.
Indexing the target with i or j alone instead of i + j (or i + j - 1 in the 1-based grid).
Skipping the length-sum guard and reading past the end of s3 on uneven inputs.
Initializing an entire first row or column to true loses the requirement that every preceding character matched.
In Python, multiplying one nested list aliases all rows. Allocate each row independently as shown.
Interview tip: define dp[i][j] using consumed prefix lengths, then derive the target index rather than memorizing an offset.

Key Takeaway

To test whether two ordered sources merge into a target, grid all prefix pairs and let each cell inherit from the top or left neighbour on a character match.