Faangprep Logo
Log inStart free
Browse curriculum

Interleaving String

Decide whether s3 is s1 and s2 woven together with a 2D DP table: each cell asks whether two prefixes can build a prefix of s3.

MediumSolve on LeetCode

Problem Understanding

Interleaving String: given strings s1, s2 and s3, return true if s3 is formed by interleaving s1 and s2: splitting both into pieces and merging them while keeping each string's letters in their original order.

Example: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" returns true; with s3 = "aadbbbaccc" it returns false.

The Intuition: Where Did the Last Letter Come From?

Reading s3 left to right, every letter is taken from the front of what is left of s1 or of s2. The state is just how many letters of each you have used: (i, j). Then i + j letters of s3 are done.

The last of those letters, s3[i + j - 1], came from one of two places:

  1. From s1: then s1[i - 1] equals it and (i - 1, j) was reachable.
  2. From s2: then s2[j - 1] equals it and (i, j - 1) was reachable.

That is a grid of true/false cells, filled row by row like Unique Paths: moving down uses a letter of s1, moving right uses a letter of s2. A true answer is a path from the top-left to the bottom-right corner. It is the same two-string table as Longest Common Subsequence and Edit Distance, with booleans instead of counts; Distinct Subsequences fills the same kind of grid with path counts.

Interactive Walkthrough

s3 sits above the table with the letter being explained lit. Each cell shows T or F; the true neighbour it came from is tinted. Try Greedy trap to see why picking the first match is not enough.

Dry Run Table

Input: s1 = "aa" (down), s2 = "ab" (across), s3 = "aaba"

∅ a b
∅ T T F
a T T T
a T F T
  • dp[2][1] is F: s3[2] = 'b', but s1[1] and s2[0] are both 'a'. That is where greedy (two a's from s1 first) gets stuck.
  • dp[1][2] is T: from dp[1][1] with s2[1] = 'b'.
  • dp[2][2] is T: from dp[1][2] with s1[1] = 'a'.

Answer: true, via a from s2, a from s1, b from s2, a from s1.

The Solution Template

A full (m + 1) × (n + 1) table, filled row by row. Cell (0, 0) skips both checks, so k = -1 is never read.

Interleaving String Code
1var isInterleave = function(s1, s2, s3) {
2    const m = s1.length, n = s2.length;
3    if (m + n !== s3.length) return false;
4    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
5    dp[0][0] = true;
6    for (let i = 0; i <= m; i++) {
7        for (let j = 0; j <= n; j++) {
8            const k = i + j - 1;
9            if (i > 0 && dp[i - 1][j] && s1[i - 1] === s3[k]) dp[i][j] = true;
10            if (j > 0 && dp[i][j - 1] && s2[j - 1] === s3[k]) dp[i][j] = true;
11        }
12    }
13    return dp[m][n];
14};

Edge Cases & Common Mistakes

  • Lengths do not add up: return false before building the table.
  • Empty strings: s1 = "", s2 = "", s3 = "" is true; with one empty input, s3 must equal the other.
  • Greedy matching: when both strings offer the next letter, either choice may be the right one. Only the table (or memoised recursion) checks both.
  • Indexing s3: cell (i, j) explains s3[i + j - 1], not s3[i + j].
  • Plain recursion without memo: tries both branches at every tie and is exponential; memoising on (i, j) gives the same O(m · n) as the table.

Summary

Check that the lengths add up. dp[i][j] is true when the cell above is true and s1[i - 1] matches s3[i + j - 1], or the cell to the left is true and s2[j - 1] matches. Return dp[m][n]. O(m · n) time, and O(n) space with a single row.

More practice: DSA interview questions with answers · patterns cheat sheet

Previous

Edit Distance

Next

Distinct Subsequences

The approach, step by step

  1. Check the lengths

    If len(s1) + len(s2) is not len(s3), return false.

  2. Fill the table

    Set dp[0][0] = true. For every (i, j), dp[i][j] is true if the cell above is true and s1[i - 1] equals s3[i + j - 1], or the cell to the left is true and s2[j - 1] equals it.

  3. Read the corner

    Return dp[m][n].

Frequently asked questions

What does dp[i][j] mean in Interleaving String?

dp[i][j] is true when the first i letters of s1 and the first j letters of s2 can be interleaved into the first i + j letters of s3. The last letter of that prefix, s3[i + j - 1], came either from s1 (so dp[i - 1][j] must be true and s1[i - 1] must match) or from s2 (dp[i][j - 1] and s2[j - 1]).

Why does a greedy two-pointer approach fail?

When the next letter of s3 matches the next letter of both s1 and s2, greedy has to pick one, and the wrong pick can get stuck later. For s1 = "aa", s2 = "ab", s3 = "aaba", taking both a's from s1 leaves "b" needing s2's "a" first. The DP keeps both options open.

Can Interleaving String use O(n) space?

Yes. Row i only reads row i - 1 and the cell to its left, so one array of length n + 1 is enough: dp[j] = (dp[j] and s1[i - 1] == s3[i + j - 1]) or (dp[j - 1] and s2[j - 1] == s3[i + j - 1]).

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description