Framework Thinking - Neetcode 150 - Inorder Shuffle

Here is solutions for Inorder Shuffle.

1. Understand the problem

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

3. Explore examples.

x y z Result Reason
“ab” “12” “ab12” ✅ x then y
“ab” “12” “a12b” ✅ interleaving valid
“ab” “12” “a21b” ❌ order of y violated
“ab” “123” “ab12” ❌ length mismatch
“ab” “cd” “ab12” ❌ extra characters
“aa” “ab” “aaba” ✅ duplicates handled
“ab” “ac” “abca” ❌ ordering breaks

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

5. Implement solutions.

class Solution:
    def isInorderShuffle(self, x: str, y: str, z: str) -> bool:
        m, n = len(x), len(y)

        # Rule 1: Total length must match
        if m + n != len(z):
            return False

        # dp[i][j] = True if x[:i] and y[:j] form z[:i+j]
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        # Fill first column (only x used)
        for i in range(1, m + 1):
            dp[i][0] = dp[i-1][0] and x[i-1] == z[i-1]

        # Fill first row (only y used)
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j-1] and y[j-1] == z[j-1]

        # Fill rest of table
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                k = i + j - 1
                dp[i][j] = (
                    (dp[i-1][j] and x[i-1] == z[k]) or
                    (dp[i][j-1] and y[j-1] == z[k])
                )

        return dp[m][n]

✅ First Column (dp[i][0])

  • Only x is used, so:
dp[i][0] = dp[i-1][0] and x[i-1] == z[i-1]

Interpretation:

  • The first i characters of x must exactly match the first i characters of z.

  • If even one character mismatches, everything below becomes False.

✅ First Row (dp[0][j])

Only y is used:

dp[0][j] = dp[0][j-1] and y[j-1] == z[j-1]

Meaning:

  • The first j characters of y must exactly match the first j characters of z.

Position k

k = i + j - 1
dp[i][j] = (
    (dp[i-1][j] and x[i-1] == z[k]) or
    (dp[i][j-1] and y[j-1] == z[k])
)

6. Dry run testcases.

December 7, 2025