Interleaving String

PracticeNeetCode ↗LeetCode ↗

Given strings s1, s2, and s3, determine whether s3 can be formed by interleaving the characters of s1 and s2 while preserving the relative order of characters within each source string.

Example

Key Pointers

• If len(s1) + len(s2) != len(s3), it's an immediate no — there's no way to interleave to the wrong length.
• Define dp[i][j] as "can the first i+j characters of s3 be built by interleaving s1[:i] and s2[:j]?" — the next character of s3 must have come from one of the two sources.
• A cell is reachable if either the last character came validly from s1 (and the state before that was reachable), or from s2 (same condition) — an OR, not an AND, since only one source needs to work.

Step-by-Step Analysis

1. If the lengths don't add up, return False immediately.
2. Build a boolean grid sized (len(s1)+1) × (len(s2)+1), with dp[0][0] = True (two empty strings trivially interleave to an empty result).
3. For each cell (i, j): it's True if s1[i-1] matches the corresponding s3 character and dp[i-1][j] is True, or if s2[j-1] matches and dp[i][j-1] is True.
4. The bottom-right cell, dp[len(s1)][len(s2)], holds the final answer.

Complexity

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

Code

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

    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    for i in range(m + 1):
        for j in range(n + 1):
            if i > 0 and s1[i - 1] == s3[i + j - 1] and dp[i - 1][j]:
                dp[i][j] = True
            if j > 0 and s2[j - 1] == s3[i + j - 1] and dp[i][j - 1]:
                dp[i][j] = True

    return dp[m][n]

Code Explanation

How the solution above works, piece by piece.

1. If the lengths don't add up, it's impossible.
2. dp[i][j] = can s1[:i] and s2[:j] interleave to form s3[:i+j]? dp[0][0] = True.
3. Coming from above: the last character came from s1, so s1[i-1] must equal s3[i+j-1] and dp[i-1][j] must be true.
4. Coming from the left: same check with s2[j-1] and dp[i][j-1].
5. dp[m][n] is the answer. O(m × n) time and space.

Visual Walkthrough

Running it on s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac":

Video Explanation

NeetCode — Dynamic Programming, LeetCode 97