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

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.

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.