Framework Thinking - Neetcode 150 - Interleaving String

Here is solutions for Interleaving String.

1. Understand the problem

You are given three strings:
- s1
- s2
- s3
You must determine whether s3 is formed by interleaving s1 and s2.
What does interleaving mean?
- You merge characters from s1 and s2
- Order of characters inside each string must be preserved
- You can switch between s1 and s2 any number of times

s1 = "abc"
s2 = "def"
Valid interleaving → "adbcef"
Invalid → "abdfec" (violates order of s2)

2. Clarify constraints, asks 4 - 5 questions including edge cases.

Length constraint:

What if len(s1) + len(s2) != len(s3)? → Then it is immediately impossible.

Empty strings allowed?

Can s1 or s2 be empty? → Yes.
If s1=””, then s3 must equal s2.

Character set?

Any ASCII? Lowercase only? → Doesn’t matter; algorithm works for any characters.

Duplicates allowed?

Yes → requires DP, not greedy.

Expected time complexity?

Brute force is exponential → must optimize with DP.

3. Explore examples.

Example 1:

s1 = "aab"
s2 = "axy"
s3 = "aaxaby"
Output = True

Example 2:

s1 = "aab"
s2 = "axy"
s3 = "abaaxy"
Output = False

Example 3 (Edge Case):

s1 = ""
s2 = "abc"
s3 = "abc"
Output = True

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Naive Solution - Time O(2^(N + M)), Space O(N + M)

At each position in s3, you decide:

Take the next character from s1 (if it matches)
OR take the next character from s2 (if it matches)

You explore all possible interleavings recursively.

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

        def dfs(i, j):
            k = i + j

            # Base case: all characters used
            if i == len(s1) and j == len(s2):
                return True

            # Try taking from s1
            if i < len(s1) and s1[i] == s3[k]:
                if dfs(i + 1, j):
                    return True

            # Try taking from s2
            if j < len(s2) and s2[j] == s3[k]:
                if dfs(i, j + 1):
                    return True

            return False

        return dfs(0, 0)

Time: O(2^(N + M))
Space: O(N + M)

4.2. DP - Top-down - Time O(N * M), Space: O(N * M)

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

        dp = {}
        def dfs(i, j):
            k = i + j

            if i == len(s1) and j == len(s2):
                return True

            if (i, j) in dp:
                return dp[(i, j)]

            res = False
            if i < len(s1) and s1[i] == s3[k]:
                res = dfs(i + 1, j)
            if not res and j < len(s2) and s2[j] == s3[k]:
                res = dfs(i, j + 1)

            dp[(i, j)] = res
            return res

        return dfs(0, 0)

Time: O(N * M)
Space: O(N * M)

4.3. DP Bottom-up - Time O(N * M), Space: O(N * M)

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)

        # Length check (mandatory)
        if m + n != len(s3):
            return False

        # dp[i][j] = whether s1[:i] and s2[:j] form s3[:i+j]
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        # First row: only s2 contributes
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]

        # First column: only s1 contributes
        for i in range(1, m + 1):
            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]

        # Fill DP table
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = (
                    (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or
                    (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
                )

        return dp[m][n]

Time: O(N * M)
Space: O(N * M)

4.4. Optimize 1D DP - Time O(N * M), Space O(min(M, N))

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)

        if m + n != len(s3):
            return False

        dp = [False] * (n + 1)
        dp[0] = True

        # First row
        for j in range(1, n + 1):
            dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]

        # Remaining rows
        for i in range(1, m + 1):
            dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
            for j in range(1, n + 1):
                dp[j] = (
                    (dp[j] and s1[i - 1] == s3[i + j - 1]) or
                    (dp[j - 1] and s2[j - 1] == s3[i + j - 1])
                )

        return dp[n]

Time: O(N * M)
Space: O(min(N, M)), fill by the min of M,N

5. Implement solutions.

6. Dry run testcases.

December 7, 2025