2026-09-23 — Interleaving String

Difficulty: 🟡 Medium Pattern: Dynamic programming (2D grid over two inputs) Time-box: 20 minutes

Problem

Given strings s1, s2 and s3, determine whether s3 can be formed by an interleaving of s1 and s2. An interleaving merges the two strings while preserving the relative order of the characters in each — e.g. "abc" and "123" interleave to "a1b2c3", "1a2b3c" or "abc123" (20 ways in total), but never to "acb123".

Return True or False.

Examples

s1="aab", s2="bc",  s3="ababc" -> True   (a·a·b and b·c woven as a b a b c)
s1="aab", s2="bc",  s3="aacbb" -> False  (s2 needs b before c, impossible here)
s1="",    s2="xyz", s3="xyz"    -> True   (one side is empty)
s1="",    s2="",    s3=""       -> True

Constraints

0 <= s1.length, s2.length <= 100, s3.length <= 200.
s3 made of an interleaving must satisfy len(s1) + len(s2) == len(s3) — check that first and bail out.
Aim for O(len(s1) * len(s2)) time; a set of "all prefixes tried so far" with memoised DFS is the common O(n*m) alternative.

Hint (open only if stuck after 10 minutes)

Define dp[i][j] = "the first i characters of s1 and the first j of s2 can interleave to exactly s3[:i+j]". The first row/column only depend on one string. For the general cell, the next character of s3 must come from s1 (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or from s2 (dp[i][j-1] and s2[j-1] == s3[i+j-1]).

Solution

def is_interleave(s1: str, s2: str, s3: str) -> bool:
    if len(s1) + len(s2) != len(s3):
        return False

    m, n = len(s1), len(s2)
    # dp[j] = first j chars of s2 interleave with the CURRENT row's
    # s1 prefix to form the matching prefix of s3.
    dp = [False] * (n + 1)
    dp[0] = True
    for j in range(1, n + 1):            # first row: s1 is empty
        dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]

    for i in range(1, m + 1):
        dp[0] = dp[0] and s1[i - 1] == s3[i - 1]  # first column
        for j in range(1, n + 1):
            k = i + j - 1                 # index of the s3 char being placed
            from_s1 = dp[j] and s1[i - 1] == s3[k]      # dp[j] is still row i-1
            from_s2 = dp[j - 1] and s2[j - 1] == s3[k]
            dp[j] = from_s1 or from_s2

    return dp[n]

How it works. Every prefix of s3 of length i+j must be built from exactly i characters of s1 and j of s2, so the problem shrinks to a grid walk: from (i, j) you could have arrived by consuming s1[i-1] (from above) or s2[j-1] (from the left), provided that character matches s3[i+j-1]. One row of the grid is enough because each cell only reads its own row and the one above.

Complexity. Time: O(mn) — one match comparison per cell. Space: O(n) — the collapsed row (O(mn) for the full table).

Edge cases that matter. Length mismatch (immediate False — the most common "works in tests, wrong in production" miss). Both strings empty. One string empty (pure prefix check). Repeated characters like "aa"/"bc"/"ababbc" where both from_s1 and from_s2 branches are simultaneously valid and must both be kept.

Common wrong answer. Updating dp[j] = ... BEFORE evaluating from_s1, so from_s1 reads the NEW row's dp[j] instead of the previous row's — the "from s1" transition then silently becomes the "from s2" transition and whole families of valid interleavings are rejected. Store both predecessors in temporaries first (as from_s1/from_s2 above), or iterate the table so the read order is unambiguous.

Found a mistake? Edit this page on GitHub.