Understanding the Problem

At first glance, this looks like a simple string matching problem: just check if we can pick characters from s1 and s2 in order to form s3. But the tricky part is the branching. When the next character in s3 matches both the next available character in s1 and s2, we have a choice. Picking the wrong one can lead us down a dead end even though a valid interleaving exists.

For example, with s1 = "aa", s2 = "ab", and s3 = "aaba", a greedy approach that always picks from s1 first would consume both 'a's from s1, then need 'b' from s2, but s3[2] is 'b' and s3[3] is 'a'. That works! But change s3 to "abaa" and the greedy approach breaks. The choices interact in complex ways because future characters constrain which path is valid.

The key observation: the state of our interleaving process is completely determined by how many characters we have used from s1 and s2. If we have used i characters from s1 and j characters from s2, then we must be at position i + j in s3. So the problem reduces to finding a path through a 2D grid from (0, 0) to (len(s1), len(s2)).

Key Constraints:

0 <= s1.length, s2.length <= 100 → With m and n both up to 100, O(m * n) is 10,000 operations, which is extremely fast. A 2D DP approach is the natural fit.
0 <= s3.length <= 200 → Since s3's length must equal s1.length + s2.length for interleaving to be possible, this gives us a quick early return check.
Lowercase English letters only → No special character handling needed. But repeating characters create the ambiguity that makes this problem interesting.

Approach 1: Recursion with Memoization (Top-Down DP)

Intuition

The most natural way to think about this problem: at each step, we are at some position in s1 (index i), some position in s2 (index j), and the corresponding position in s3 is i + j. We need to decide whether to take the next character from s1 or s2.

If s1[i] matches s3[i + j], we can try consuming that character from s1 and recursing with (i + 1, j). Similarly, if s2[j] matches s3[i + j], we try (i, j + 1). If either path succeeds, the answer is true.

The "aha moment" here is that the state (i, j) completely determines where we are in the problem. We do not need to track our position in s3 separately because it is always i + j. And since many different orderings of choices can lead to the same (i, j) state, memoization eliminates redundant work.

Algorithm

If the lengths of s1 and s2 do not sum to the length of s3, return false immediately.
Define a recursive function dfs(i, j) that returns whether s3[i+j...] can be formed by interleaving s1[i...] and s2[j...].
Base case: if i == len(s1) and j == len(s2), we have matched all of s3, so return true.
If s1[i] == s3[i + j], recursively check dfs(i + 1, j).
If s2[j] == s3[i + j], recursively check dfs(i, j + 1).
Memoize results for each (i, j) pair to avoid recomputation.

Example Walkthrough

1dfs(0,0): s3[0]='a', s1[0]='a' match, s2[0]='d' no match. Try s1.

i+j=0

1/6

Code

Complexity Analysis

Time Complexity: O(m n). There are (m + 1) (n + 1) possible states, and each state is computed at most once thanks to memoization. Each state does O(1) work.
Space Complexity: O(m n). The memoization table has (m + 1) (n + 1) entries. The recursion stack can go up to depth m + n in the worst case, but that is dominated by the table.

The recursion has function call overhead and stack space. What if we filled the DP table iteratively instead, eliminating the recursion entirely?

Approach 2: Bottom-Up DP (2D Table)

Intuition

The top-down approach reveals the structure: we have a 2D state space where dp[i][j] means "can the first i characters of s1 and the first j characters of s2 interleave to form the first i + j characters of s3?"

Instead of starting from (0, 0) and recursing forward, we fill the table from the base case outward. The cell dp[i][j] is true if either:

dp[i - 1][j] is true AND s1[i - 1] == s3[i + j - 1] (we extend by taking one more character from s1), or
dp[i][j - 1] is true AND s2[j - 1] == s3[i + j - 1] (we extend by taking one more character from s2).

Why does this work?

The recurrence captures exactly the two ways to extend a valid interleaving: either the last character came from s1 or from s2. If dp[i-1][j] is true, it means we already have a valid interleaving using i-1 characters from s1 and j from s2. Adding one more character from s1 extends this to dp[i][j], but only if that character matches s3[i+j-1]. The same logic applies when extending from dp[i][j-1] with a character from s2.

The base cases handle the edges: dp[0][0] = true because empty strings interleave to form an empty string, and the first row/column handle the cases where we only use one of the two strings.

Algorithm

If len(s1) + len(s2) != len(s3), return false.
Create a boolean table dp of size (m + 1) x (n + 1).
Set dp[0][0] = true (empty strings interleave to form empty string).
Fill the first row: dp[0][j] is true if all characters of s2[0..j-1] match s3[0..j-1].
Fill the first column: dp[i][0] is true if all characters of s1[0..i-1] match s3[0..i-1].
For each cell dp[i][j], check if we can arrive from the top (using s1) or from the left (using s2).
Return dp[m][n].

Example Walkthrough

1Initialize dp[0][0]=true (empty strings interleave to form empty)

true

false

1/7

Code

Complexity Analysis

Time Complexity: O(m n). We fill a table with (m + 1) (n + 1) cells, doing O(1) work per cell.
Space Complexity: O(m n). The 2D boolean table has (m + 1) (n + 1) entries.

The 2D table uses O(m * n) space, but when computing row i, we only look at row i - 1 and the current row. Can we collapse the table into a single 1D array?

Approach 3: Space-Optimized DP (1D Array)

Intuition

Looking at the recurrence more carefully, dp[i][j] depends on only two cells: dp[i-1][j] (directly above) and dp[i][j-1] (directly to the left). This is the classic pattern that allows us to reduce a 2D DP table to a 1D array.

We maintain a single array dp of size n + 1, where dp[j] represents the current row's value. Before we update dp[j] for the current row, it still holds the value from the previous row, which is exactly dp[i-1][j]. And dp[j-1] has already been updated for the current row (since we process left to right), so it represents dp[i][j-1].

Why does this work?

The key insight is in how we reuse the array. When we start processing row i, dp[j] still contains the value from row i-1 (because we haven't updated it yet for the current row). That is exactly the "from above" value we need. Meanwhile, dp[j-1] has already been updated for the current row i (because we process left to right), so it gives us the "from left" value. This dual role of the array, holding both old and new values simultaneously, is what makes the 1D optimization work.

Algorithm

If len(s1) + len(s2) != len(s3), return false.
Create a 1D boolean array dp of size n + 1.
Set dp[0] = true.
Fill the first row: for each j, dp[j] = dp[j-1] && s2[j-1] == s3[j-1].
For each row i from 1 to m:

Update dp[0] for this row: dp[0] = dp[0] && s1[i-1] == s3[i-1].
For each column j from 1 to n: dp[j] = (dp[j] && s1[i-1] == s3[i+j-1]) || (dp[j-1] && s2[j-1] == s3[i+j-1]).

Return dp[n].

Example Walkthrough

1Initialize first row: dp[0]=T, dp[1..5]=F (s2[0]='d'!=s3[0]='a')

true

false

1/6

Code

Complexity Analysis

Time Complexity: O(m * n). Same nested loop structure as the 2D approach. We still compute every cell once.
Space Complexity: O(n). We use a single 1D array of size n + 1 instead of a 2D table.

Interleaving String

Understanding the Problem

Key Constraints:

Approach 1: Recursion with Memoization (Top-Down DP)

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Bottom-Up DP (2D Table)

Intuition

Algorithm

Example Walkthrough

Code

Approach 3: Space-Optimized DP (1D Array)

Intuition

Algorithm

Example Walkthrough

Code

Get Premium