4.24.6 — Interleaving String

LeetCode 97 · Medium

The problem

Return true if s3 can be formed by interleaving s1 and s2 — taking characters from each in turn, without reordering either.

s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"   →  true
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"   →  false

Constraints:

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

Plain-English Restatement: You have three strings. You want to know if you can build the third string by mixing the characters of the first two strings, keeping the original order of characters from both strings intact. Imagine two decks of cards, one red (s1) and one blue (s2). If you riffle shuffle them together perfectly or imperfectly to form a single deck (s3), can you get the exact sequence of cards in s3?

Brute Force Approach: You could write a recursive function with two pointers, i for s1 and j for s2. At each step, if s1[i] == s3[i+j], you can try advancing i. If s2[j] == s3[i+j], you can try advancing j.

• Time Complexity: O(2^{m+n}). Every time both strings match the target character, the recursion branches into two paths. In the worst case (e.g., all strings are just repeating "a"s), this blows up exponentially.
• Why it's wasteful: If we advance i then j, or j then i, both paths might land us at the exact same state (i+1, j+1). Evaluating the rest of the string from that state twice is redundant. DP memoizes this state.

Why greedy fails

The tempting rule is: at each character of s3, take from whichever string matches.

Break it. s1 = "a", s2 = "ab", s3 = "aab". The first a of s3 could come from either string. Take it from s1 and the rest works. Take it from s2 and you are stuck.

A choice now blocks options later, so it is DP — the structural tell from 4.22.

The pattern

Two input strings, so a 2-D grid — the recognition step from 4.24.2.

Let dp[i][j] be true when the first i characters of s1 and the first j of s2 can interleave to form the first i + j characters of s3.

s3's position is not a third dimension. It is always i + j, because every character consumed comes from exactly one of the two strings. Realising that is what keeps the table two-dimensional instead of three, and it is the main insight here.

Then the recurrence asks where the last character of s3 came from:

dp[i][j] = \big(dp[i-1][j] \ \text{and}\ s1[i-1] = s3[i+j-1]\big) \ \text{or}\ \big(dp[i][j-1] \ \text{and}\ s2[j-1] = s3[i+j-1]\big)

It came from s1 and the rest interleaves, or it came from s2 and the rest interleaves.

dp[0][0] = True — three empty strings interleave trivially.

The length check

If len(s1) + len(s2) != len(s3), the answer is immediately false. One line, and it rejects a whole class of inputs before any work.

The solution

Python

class Solution:
    def isInterleave(self, 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

        for i in range(m + 1):
            for j in range(n + 1):
                if i > 0 and dp[i-1][j] and s1[i-1] == s3[i+j-1]:
                    dp[i][j] = True
                if j > 0 and dp[i][j-1] and s2[j-1] == s3[i+j-1]:
                    dp[i][j] = True

        return dp[m][n]

TypeScript

function isInterleave(s1: string, s2: string, s3: string): boolean {
  const m = s1.length, n = s2.length;
  if (m + n !== s3.length) return false;

  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  dp[0][0] = true;

  for (let i = 0; i <= m; i++) {
    for (let j = 0; j <= n; j++) {
      if (i > 0 && dp[i-1][j] && s1[i-1] === s3[i+j-1]) dp[i][j] = true;
      if (j > 0 && dp[i][j-1] && s2[j-1] === s3[i+j-1]) dp[i][j] = true;
    }
  }

  return dp[m][n];
}

The loops start at 0, not 1, so the first row and first column are filled by the same code. Row 0 means "use nothing from s1", and it becomes true only where s2's prefix matches s3's prefix exactly — which the second condition handles.

The i > 0 and j > 0 guards prevent indexing dp[-1], which in Python would silently wrap round to the last row and give wrong answers rather than an error. That silent wrap is a real Python hazard worth naming.

s3[i + j - 1] is the character being consumed — position i + j in one-based terms, so i + j - 1 zero-based.

Trace

s1 = "a", s2 = "b", s3 = "ab".

• dp[0][0] = True.
• dp[1][0]: from s1, s1[0] = 'a' and s3[0] = 'a' ✓ → true.
• dp[0][1]: from s2, s2[0] = 'b' and s3[0] = 'b' ✓ → true.
• dp[1][1]: from s1 needs dp[0][1] (true) and s1[0] = 'a' against s3[1] = 'b' ✗. From s2 needs dp[1][0] (true) and s2[0] = 'b' against s3[1] = 'b' ✓ → true.

Space optimisation

Each row reads only the previous row and the current one, so one row suffices:

dp = [False] * (n + 1)
dp[0] = True
for j in range(1, n + 1):
    dp[j] = dp[j-1] and s2[j-1] == s3[j-1]        # row 0

for i in range(1, m + 1):
    dp[0] = dp[0] and s1[i-1] == s3[i-1]           # column 0 for this row
    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]

dp[j] still holds the previous row when read, and dp[j-1] holds the current row — the same pairing as 4.24.1 Unique Paths. dp[0] must be updated first each row, before the inner loop reads it.

O(n) space.

Complexity

O(mn) time, O(mn) or O(n) space.

The brute force is O(2^{m+n}) — every choice of which string to take from — so the table turns an exponential into a product.

Code Walkthrough

1. Length Check: if m + n != len(s3): return False. We must use all characters exactly once, so the lengths must sum perfectly.
2. DP Grid Initialization: dp = [[False] * (n + 1) for _ in range(m + 1)]. A 2D grid where dp[i][j] represents using i characters from s1 and j characters from s2.
3. Base Case: dp[0][0] = True. Two empty strings perfectly interleave to form an empty string.
4. Nested Loops: We iterate i from 0 to m and j from 0 to n.
5. Take from s1: if i > 0 and dp[i-1][j] and s1[i-1] == s3[i+j-1]: dp[i][j] = True. We can arrive at state (i, j) by taking the last character from s1, IF the previous state (i-1, j) was valid AND the current character in s1 matches the corresponding character in s3.
6. Take from s2: if j > 0 and dp[i][j-1] and s2[j-1] == s3[i+j-1]: dp[i][j] = True. Similarly, we can arrive at (i, j) from (i, j-1) if the s2 character matches.

Complexity Derivation

• Time Complexity: O(m \times n). We initialize and fill a 2D matrix of size (m+1) \times (n+1). Inside the loops, we perform O(1) operations (bounds checking, boolean checks, and character comparisons).
• Space Complexity: O(m \times n) for the full 2D table. The optimized 1D version reduces this to O(n) by only keeping the current and previous rows, since the recurrence dp[i][j] only ever looks at dp[i-1][j] (directly above) and dp[i][j-1] (directly left).

Edge Cases

• Empty Strings: If s1 and s2 are empty, it only returns true if s3 is also empty. This is handled gracefully.
• One String is Empty: If s1 is empty, the logic effectively just checks if s2 == s3, which is correct.
• Length Mismatch: Handled efficiently at the very top.

Where this goes next

• Longest Common Subsequence — the same grid, different recurrence. 4.24.2.
• Distinct Subsequences, Edit Distance — same grid again.
• Merge intervals of two sorted streams — the same "which source did this element come from" reasoning, and the reason merge in merge sort is stable.

The recognition rule for the whole chapter: two sequences means a grid with one axis each. The only question left is what the two cases are at each cell.

What the interviewer will push on

"Why not greedy?" Give the "a", "ab", "aab" counterexample.

"Why is the table 2-D and not 3-D?" The position in s3 is always i + j. This is the question the problem exists to ask.

"What is the base case?" dp[0][0] = True, and the first row and column follow from the same code.

"Why the length check?" An interleaving uses every character of both strings exactly once.

"Can you use O(n) space?" One row, updating dp[0] first.

One thing to volunteer: say i + j out loud before writing anything. It is the observation that collapses a three-dimensional-looking problem into a two-dimensional one, and it is the whole reason this problem is tractable.

Next: 4.24.7 Longest Increasing Path in a Matrix — DP on a grid where the fill order is not obvious, so memoised recursion finds it for you.