Dynamic Programming crash course ↗ · 66

97. Interleaving String

Given three strings s1, s2, and s3, determine whether s3 can be formed by interleaving the characters of s1 and s2while preserving each string's relative order. A classic 2D DP grid tracks reachability cell by cell.

● Medium2D DPString DPTypeScript

PROBLEM What we're solving

You're given s1 = "aab", s2 = "axy", and s3 = "aaxaby". Is s3 an interleaving of s1 and s2? Yes — one valid split is: s1[0]+s2[0..1]+s1[1]+s2[2]+s1[2] → aaxayb = aaxayb… wait, let's be precise: take a from s1, ax from s2, a from s1, b from s1, y from s2 → aaxaby. The relative order within each source string is preserved. Return true. For s1="aabcc", s2="dbbca", s3="aadbbcbcac" → false.

KEY IDEA Track reachable (i, j) prefixes in a 2D grid

Insight → define dp[i][j] = "can s3[0..i+j) be formed by interleaving s1[0..i) and s2[0..j)". Each cell only depends on the cell directly above (we took a char from s1) or directly to the left (we took a char from s2). The answer is dp[m][n]. This turns an exponential branching search into an O(m·n) table fill.

RECURRENCE Fill the grid row by row

  • 0 · Length check. If m + n ≠ |s3|, return false immediately — no interleaving can work.
  • 1 · Base case. dp[0][0] = true — empty prefixes of s1 and s2 trivially form the empty prefix of s3.
  • 2 · First row (i=0, use only s2). dp[0][j] = dp[0][j-1] && s2[j-1] === s3[j-1]. We can only advance along s2 as long as every character matches.
  • 3 · First column (j=0, use only s1). Symmetric: check against s3[i-1].
  • 4 · Interior cells. k = i + j - 1 is the s3 index to match. dp[i][j] = (dp[i-1][j] && s1[i-1]===s3[k]) || (dp[i][j-1] && s2[j-1]===s3[k]). "From above" means the last char came from s1; "from left" means it came from s2.
  • 5 · Answer. Return dp[m][n].
Classic confusion → the s3 index is k = i + j - 1, not i or j. Many learners accidentally index s3 with i-1 or j-1 and get wrong answers on overlapping characters. Remember: after consuming i chars of s1 and j chars of s2, the next s3 position is i+j-1 (0-indexed).

COST Complexity & space optimisation

Naive recursion
O(2^(m+n))
Each character branches: take from s1 or from s2.
2D DP table
O(m·n)
O(m·n) time; O(m·n) space — or O(n) with a rolling row.

Space reduction

Because each row only reads from the row above, you can keep a single boolean[n+1] row and overwrite it in place, reducing space to O(n). The update becomes: dp[j] = (dp[j] && s1[i-1]===s3[k]) || (dp[j-1] && s2[j-1]===s3[k]).

Pattern transfer →the same "can prefix of A interleave with prefix of B to form prefix of C" structure appears in Edit Distance (cost of aligning two strings), Distinct Subsequences (count ways s appears in t), and Regular Expression Matching (match two strings with wildcards). Any time you need to track progress through two sequences simultaneously, reach for a 2D DP grid.

RUN IT Fill dp[i][j]: can s1[0..i)+s2[0..j) form s3[0..i+j)

step 0 / 17
STARTs1=aab, s2=axy, s3=aaxaby. Lengths sum correctly. Build dp[4][4] where dp[i][j] = can s3[0..i+j) be formed by interleaving s1[0..i) and s2[0..j).
1▶function isInterleave(s1: string, s2: string, s3: string): boolean {
2▶  const m = s1.length, n = s2.length;
3  if (m + n !== s3.length) return false;          // length precondition
4 
5  // dp[i][j] = can s3[0..i+j) be formed by interleaving s1[0..i) and s2[0..j)
6▶  const dp: boolean[][] = Array.from({ length: m + 1 },
7▶    () => new Array(n + 1).fill(false));
8 
9  dp[0][0] = true;                                // empty + empty = empty
10 
11  for (let j = 1; j <= n; j++)                    // first row: use only s2
12    dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];
13 
14  for (let i = 1; i <= m; i++)                    // first col: use only s1
15    dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];
16 
17  for (let i = 1; i <= m; i++) {
18    for (let j = 1; j <= n; j++) {
19      const k = i + j - 1;                        // next char of s3 to match
20      dp[i][j] =
21        (dp[i - 1][j] && s1[i - 1] === s3[k]) || // take from s1 (match up)
22        (dp[i][j - 1] && s2[j - 1] === s3[k]);   // take from s2 (match left)
23    }
24  }
25 
26  return dp[m][n];
27}
a
x
y
·
·
·
·
a
·
·
·
·
a
·
·
·
·
b
·
·
·
·
State
i: —
j: —
current cellsource (true) cellreachable (true)unreachable (false)
slowfast

TYPESCRIPT The solution, annotated

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

  // dp[i][j] = can s3[0..i+j) be formed by interleaving s1[0..i) and s2[0..j)
  const dp: boolean[][] = Array.from({ length: m + 1 },
    () => new Array(n + 1).fill(false));

  dp[0][0] = true;                                // empty + empty = empty

  for (let j = 1; j <= n; j++)                    // first row: use only s2
    dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];

  for (let i = 1; i <= m; i++)                    // first col: use only s1
    dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const k = i + j - 1;                        // next char of s3 to match
      dp[i][j] =
        (dp[i - 1][j] && s1[i - 1] === s3[k]) || // take from s1 (match up)
        (dp[i][j - 1] && s2[j - 1] === s3[k]);   // take from s2 (match left)
    }
  }

  return dp[m][n];
}

Reading it block by block

Line 3 — cheap reject. If m + n !== s3.length, no interleaving is possible — the characters can't sum up. This single guard avoids all the work below.
Lines 6–8 — allocate the DP table. A (m+1) × (n+1) grid of booleans, all false initially. The +1 accounts for the empty-prefix base cases.
Line 10 — base case. dp[0][0] = true — consuming zero chars from both s1 and s2 trivially forms the empty s3.
Lines 12–13 — first row. With i=0 we can only draw from s2. Each cell propagates only if the previous cell was reachable AND the next s2 character matches s3.
Lines 15–16 — first column. Symmetric: with j=0 we can only draw from s1.
Lines 18–24 — interior fill. k = i + j - 1 is the next s3 position. The cell is true if we can legally arrive via the cell above (took s1[i-1]) or the cell to the left (took s2[j-1]).
Line 26 — answer. dp[m][n] answers whether all of s1 and all of s2 were consumed while matching all of s3.
Complexity → O(m·n) time — we fill every cell exactly once. O(m·n) space for the table; reducible to O(n) with a single rolling row since each row only reads from the row above.

INTERVIEWFollow-ups they'll ask

  • "Can you reduce the space?" Yes — a single boolean[n+1] row updated in place gives O(n) space. The update rule is dp[j] = (dp[j] && s1[i-1]===s3[k]) || (dp[j-1] && s2[j-1]===s3[k]).
  • "What if you need to return the actual interleaving?" Store a parent pointer at each cell (up or left), then backtrack from dp[m][n] to reconstruct which source each character came from.
  • "What's the brute force?" Recursive branching — at each step try taking the next char from s1 or s2, two branches total. O(2^(m+n)) without memoisation, O(m·n) with it (same as the DP table).
  • "What if there are three strings to interleave?" Extend to 3D DP: dp[i][j][k] — same principle, O(l·m·n) time and space.
  • Edge cases: empty s1 or s2 (answer is s3 === s2 or s3 === s1), all-same characters (the count check passes but positions may not), s3 longer or shorter than s1+s2 (caught by the length guard).

OPTIMAL 2D DP

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

  // dp[i][j] = can s3[0..i+j) be formed by interleaving s1[0..i) and s2[0..j)
  const dp: boolean[][] = Array.from({ length: m + 1 },
    () => new Array(n + 1).fill(false));

  dp[0][0] = true;                                // empty + empty = empty

  for (let j = 1; j <= n; j++)                    // first row: use only s2
    dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];

  for (let i = 1; i <= m; i++)                    // first col: use only s1
    dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const k = i + j - 1;                        // next char of s3 to match
      dp[i][j] =
        (dp[i - 1][j] && s1[i - 1] === s3[k]) || // take from s1 (match up)
        (dp[i][j - 1] && s2[j - 1] === s3[k]);   // take from s2 (match left)
    }
  }

  return dp[m][n];
}
Complexity → O(m·n) time — we fill every cell exactly once. O(m·n) space for the table; reducible to O(n) with a single rolling row since each row only reads from the row above.

ALT 1 Brute force — recurse on which string supplies the next char

O(2^(m+n)) time · O(m + n) space

At each step the next character of s3 must come from s1 or s2. Try both whenever they match and recurse; succeed when all three are exhausted.

approach-2.ts
function isInterleave(s1: string, s2: string, s3: string): boolean {
  if (s1.length + s2.length !== s3.length) return false;

  function rec(i: number, j: number): boolean {
    const k = i + j;
    if (k === s3.length) return true;          // consumed everything
    // take next char from s1
    if (i < s1.length && s1[i] === s3[k] && rec(i + 1, j)) return true;
    // take next char from s2
    if (j < s2.length && s2[j] === s3[k] && rec(i, j + 1)) return true;
    return false;
  }

  return rec(0, 0);
}
Note → With two branches per character, the worst case is O(2^(m+n)) and the same (i, j) pair is revisited exponentially often. Memoising on (i, j)— or the iterative grid — collapses it to O(m·n).

MNEMONIC The one-liner

"Each cell asks: did I arrive from above (s1) or from the left (s2)? Match the next s3 char and inherit reachability."

TRIGGERS When you see ___ → reach for ___

"interleave / merge two strings preserving order"2D DP grid dp[i][j]
track progress through two sequences simultaneously(m+1)×(n+1) boolean table
length check before anythingif m+n !== s3.length return false
"reduce space of 2D DP"rolling 1D row — only needs previous row

SKELETON The reusable shape

skeleton.ts
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 j = 1; j <= n; j++) dp[0][j] = dp[0][j-1] && s2[j-1] === s3[j-1];
  for (let i = 1; i <= m; i++) dp[i][0] = dp[i-1][0] && s1[i-1] === s3[i-1];

  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++) {
      const k = i + j - 1;
      dp[i][j] = (dp[i-1][j] && s1[i-1] === s3[k]) ||
                 (dp[i][j-1] && s2[j-1] === s3[k]);
    }

  return dp[m][n];
}

FLASHCARDS Tap to flip

What does dp[i][j] represent?
Can s3[0..i+j) be formed by interleaving s1[0..i) and s2[0..j)?
tap to flip
1 / 8
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
What is dp[i][j] in the interleaving string DP?
QUESTION 02
s1="ab", s2="cd", s3="acbd". What is dp[1][1]?
QUESTION 03
What is the time complexity of the 2D DP solution?
QUESTION 04
Which s3 index does dp[i][j] use for its character match?
QUESTION 05
What is the first thing the algorithm should check?
QUESTION 06
How can you reduce the space complexity from O(m·n) to O(n)?
QUESTION 07
In the recurrence, "from above" (dp[i-1][j]) corresponds to:
QUESTION 08
#97 · Interleaving String2D DP where dp[i][j] asks whether s3[0..i+j) can be formed by interleaving s1[0..i) and s2[0..j). A cell is true when the matching character was taken from above (dp[i−1][j]) or from the left (dp[i][j−1]).Which algorithmic approach does this primarily use?
QUESTION 09
#97 · Interleaving String2D DP where dp[i][j] asks whether s3[0..i+j) can be formed by interleaving s1[0..i) and s2[0..j). A cell is true when the matching character was taken from above (dp[i−1][j]) or from the left (dp[i][j−1]).Which implementation correctly solves it?