Skip to content

146 — Interleaving String

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

146 — Interleaving String

LeetCode 97 · Medium. Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2. An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that the substrings are concatenated alternately, preserving the relative order of characters from each original string (with some flexibility in how the division is done — either string can contribute any number of consecutive characters at each step).

🍽️ Intuition

Picture reading s3 one character at a time and, at every point, asking "did that last character come from s1 or from s2?" To answer "can s3's first i+j characters be built by interleaving s1's first i characters with s2's first j characters," you only need to know two smaller answers: could you build it using one less character of s1 (and the same amount of s2), or one less character of s2 (and the same amount of s1)? Both of those are the exact same question, just with one index nudged down by one — a state described by two indices into two source strings, which is the signature of 2-D DP.

🚩 Pattern-Recognition Cue

"Is s3 an interleaving of s1 and s2" is the classic two-source-index tell: the state is (how far into s1, how far into s2), and a cell is reachable only from directly above (consumed one more character of s1) or directly to the left (consumed one more character of s2) — never diagonally, since each step consumes from exactly one source string.

🐢 Brute Force

Recurse over (i, j), the number of characters consumed from s1 and s2 so far, trying to extend from whichever source's next character matches the next character of s3, with no memoization.

func isInterleaveBruteForce(_ s1: String, _ s2: String, _ s3: String) -> Bool {
    let a = Array(s1), b = Array(s2), c = Array(s3)
    guard a.count + b.count == c.count else { return false }

    func dfs(_ i: Int, _ j: Int) -> Bool {
        let k = i + j
        if k == c.count { return true }

        if i < a.count && a[i] == c[k] && dfs(i + 1, j) {
            return true
        }
        if j < b.count && b[j] == c[k] && dfs(i, j + 1) {
            return true
        }
        return false
    }

    return dfs(0, 0)
}

// smoke test
print(isInterleaveBruteForce("aabcc", "dbbca", "aadbbcbcac"))   // true
print(isInterleaveBruteForce("aabcc", "dbbca", "aadbbbaccc"))   // false
print(isInterleaveBruteForce("", "", ""))                        // true

Big-O: O(2^(m+n)) time in the worst case — every position where both sources could match branches two ways, and the same (i, j) pairs are re-explored down many different branches. O(m + n) space for the recursion stack.

🚀 Optimal

Fill an (m+1) x (n+1) table where dp[i][j] is true if s3's first i+j characters can be formed by interleaving s1's first i characters with s2's first j characters.

func isInterleave(_ s1: String, _ s2: String, _ s3: String) -> Bool {
    let a = Array(s1), b = Array(s2), c = Array(s3)
    let m = a.count, n = b.count
    guard m + n == c.count else { return false }

    var dp = Array(repeating: Array(repeating: false, count: n + 1), count: m + 1)
    dp[0][0] = true

    for i in 0...m {
        for j in 0...n {
            if i == 0 && j == 0 { continue }

            var canForm = false
            if i > 0 && dp[i - 1][j] && a[i - 1] == c[i + j - 1] {
                canForm = true
            }
            if !canForm && j > 0 && dp[i][j - 1] && b[j - 1] == c[i + j - 1] {
                canForm = true
            }
            dp[i][j] = canForm
        }
    }

    return dp[m][n]
}

// smoke test — same cases as the brute force
print(isInterleave("aabcc", "dbbca", "aadbbcbcac"))   // true
print(isInterleave("aabcc", "dbbca", "aadbbbaccc"))   // false
print(isInterleave("", "", ""))                        // true

Big-O: O(m · n) time — every cell is filled exactly once from its up and left neighbors. O(m · n) space for the dp table (collapsible to O(n) with a single rolling row).

🔑 The Key Insight

Both versions ask the same question at every (i, j) — can the next character of s3 be explained by the next unused character of s1, or of s2? — but the brute force treats every (i, j) as fresh no matter how many paths reach it, so the same index pairs are re-solved exponentially many times. The optimal version fills the table row by row, so dp[i-1][j] and dp[i][j-1] are always already-finished answers by the time dp[i][j] needs them. Reusing two already-solved neighbors instead of re-branching from scratch is what turns exponential interleaving checks into a flat O(m · n) table fill.

🔗 Related Chapters

  • 2D Dynamic Programming — two source sequences, one on each axis, a table filled from up/left neighbors only (no diagonal, since a character always comes from exactly one source) — the same two-sequence recognition signal chapter 27 describes.
  • Arrays and Strings — all three strings are converted to [Character] arrays for O(1) indexed access, and dp is a plain 2-D boolean array.

🧸 Memory Sentence

Interleaving String never looks diagonally — each cell can only come from consuming one more character of s1 (up) or one more of s2 (left), because every character of s3 came from exactly one source.

✅ Check Your Understanding

  1. Why does dp[i][j] never reference dp[i-1][j-1] the way Longest Common Subsequence does? What would consuming a character from both strings at once even mean here?
  2. Trace isInterleave("ab", "c", "cab") by hand-filling the small 3 x 2 table. Which cells end up true, and why does dp[1][0] (using one character of s1, none of s2) come out false?
  3. The initial guard checks m + n == c.count. Why is this a correctness requirement rather than just a performance shortcut — what would happen if you skipped it and s3 were the wrong length?

⬅️ Previous: Target Sum · Next: Longest Increasing Path in a Matrix ➡️

Clone this wiki locally