Framework Thinking - Axon - Inorder Shuffle

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.

All characters in x & y are in z.

This also goes vice versa - all characters in z are in x & y. This nuance adds an edge case to the problem where z cannot have extra characters that aren’t in x or y.

Sometimes the candidate will realize that this implies len(x) + len(y) = len(z), which is a good thing.

Sometimes candidates can get confused slightly by duplicate characters. If they ask about this in an articulate way that’s a really good thing. For example, “if x or y contains two of the same character, does z need to contain the same number of that character?” (answer is yes)

The order of the characters in z is the same as the order of the characters in x & y.

(I like to be verbose here - I’ll say something like: “For example, if you look at x, the ‘a’ comes before the ‘b’. This is the same as in z. You can do the same with y and z)

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)

def isInorderShuffle(x, y, z):
   return shuffleHelper(x, y, z, 0, 0, 0)

def shuffleHelper(x, y, z, xptr, yptr, zptr):
   retrecursex = False
   retrecursey = False
   print(str(xptr) + ' ' + str(yptr) + ' ' + str(zptr))
   if (xptr == len(x) and yptr == len(y) and zptr == len(z)):
       return True
   else:
       if (xptr < len(x) and zptr < len(z) and x[xptr] == z[zptr]):
           retrecursex = shuffleHelper(x, y, z, xptr + 1, yptr, zptr + 1)
       if (yptr < len(y) and zptr < len(z) and y[yptr] == z[zptr]):
           retrecursey = shuffleHelper(x, y, z, xptr, yptr + 1, zptr + 1)
       return retrecursex or retrecursey

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

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

d[i,j] = whether s3[:i + j] can form from s1[:i], s2[:j]
Use Memorize DP because:

dfs(1,1) reached from dfs(0,1) and dfs(1,0)
dfs(2,1) reached from many paths

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