Interleaving String

Difficulty: Medium

You're given three strings, s1, s2, and s3. Determine whether s3 can be formed by interleaving the characters of s1 and s2 — shuffling them together — while keeping each string's own characters in their original left-to-right order.

Think of it like riffle-shuffling two decks of cards: the cards from each deck stay in their own order, but cards from the two decks can end up mixed together in the result.

Examples

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

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

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

Constraints

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
All three strings contain only lowercase English letters

Approach

Build a table where cell (i, j) means: "can the first i +j characters of s3 be assembled from exactly the first i characters of s1 and the first j characters of s2?" Since every character of s3 must come from one of the two strings, the position in s3 you're up to is always exactly i + j — you never need to track it separately.

Cell (i, j) is true if either: the cell above it, (i-1, j), was true and the next character of s1 matches the next character needed in s3; or the cell to its left, (i, j-1), was true and the next character of s2 matches. If neither path works, this cell is false.

The base case (0, 0) is true (two empty prefixes trivially match an empty result so far), and the answer you want is the bottom-right corner, (len(s1), len(s2)).

Solutions

Brute Force — Recursion

At each step, track how far into s1 and s2 you are (their sum tells you how far into s3 you are). Try consuming the next character from s1 if it matches, or from s2 if it matches, and recurse. This revisits the same (i, j) pair through many different paths.

function isInterleave(s1, s2, s3) {
  if (s1.length + s2.length !== s3.length) return false;

  function solve(i, j) {
    const k = i + j;
    if (i === s1.length && j === s2.length) return true;

    let ok = false;
    if (i < s1.length && s1[i] === s3[k]) ok = solve(i + 1, j);
    if (!ok && j < s2.length && s2[j] === s3[k]) ok = solve(i, j + 1);
    return ok;
  }

  return solve(0, 0);
}

Time: O(2^(m + n)) in the worst case · Space: O(m + n) — recursion depth

Optimal — Bottom-Up 2D Table

Build a boolean table over (prefix length of s1, prefix length of s2), filling it in from the top-left base case using only cells already computed.

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

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

  for (let i = 0; i <= m; i++) {
    for (let j = 0; j <= n; j++) {
      if (i === 0 && j === 0) continue;

      const k = i + j - 1; // index into s3 of the character just placed
      let ok = false;
      if (i > 0 && table[i - 1][j] && s1[i - 1] === s3[k]) ok = true;
      if (!ok && j > 0 && table[i][j - 1] && s2[j - 1] === s3[k]) ok = true;
      table[i][j] = ok;
    }
  }

  return table[m][n];
}

Time: O(m * n) · Space: O(m * n)