Problem Description

You are given three strings s1, s2, and s3. You need to determine whether s3 can be formed by interleaving s1 and s2.

An interleaving of two strings s and t means:

• Both strings are divided into multiple non-empty substrings
• s is divided into n substrings: s = s₁ + s₂ + ... + sₙ
• t is divided into m substrings: t = t₁ + t₂ + ... + tₘ
• The difference between the number of substrings must satisfy: |n - m| ≤ 1
• The substrings are alternately combined to form the interleaved string in one of these patterns:
  • s₁ + t₁ + s₂ + t₂ + s₃ + t₃ + ...
  • t₁ + s₁ + t₂ + s₂ + t₃ + s₃ + ...

In simpler terms, you need to check if s3 can be formed by taking characters from s1 and s2 while:

• Maintaining the relative order of characters from each original string
• Using all characters from both s1 and s2 exactly once
• The resulting string equals s3

For example:

• If s1 = "aab", s2 = "axy", and s3 = "aaxaby", then s3 is a valid interleaving because we can form it by taking characters alternately while preserving order: a from s1, a from s1, x from s2, a from s2, b from s1, y from s2.

The concatenation operator + simply means joining strings together.

Intuition

Think of this problem as making choices at each step: when building s3, we need to decide whether the current character comes from s1 or s2.

Imagine you have two pointers, one for s1 and one for s2, starting at the beginning of each string. At any point, you're trying to match the current position in s3. The key insight is that the position in s3 is always the sum of how far you've progressed in both s1 and s2 - if you've used i characters from s1 and j characters from s2, you're at position i + j in s3.

At each step, you have at most two choices:

1. If the current character in s1 matches the current position in s3, you can choose to take from s1 and move its pointer forward
2. If the current character in s2 matches the current position in s3, you can choose to take from s2 and move its pointer forward

This naturally leads to a recursive solution where we explore both possibilities when available. The base case is when we've used all characters from both s1 and s2 - if we've also matched all of s3, then we've found a valid interleaving.

The first optimization is obvious: if the total length of s1 and s2 doesn't equal the length of s3, it's impossible to form an interleaving, so we can return false immediately.

The second optimization comes from recognizing that we might encounter the same subproblem multiple times - the same (i, j) pair might be reached through different paths. For instance, taking character 1 from s1 then character 1 from s2 leads to the same state as taking character 1 from s2 then character 1 from s1. This overlap in subproblems makes memoization effective, where we cache the result for each (i, j) pair to avoid redundant calculations.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses memoization search (also known as top-down dynamic programming) to efficiently solve the problem.

Implementation Details:

1. Initial Check: First, we check if len(s1) + len(s2) == len(s3). If not, it's impossible to form s3 from s1 and s2, so we return false immediately.

2. Recursive Function with Memoization: We define a function dfs(i, j) where:

   • i represents the current index in string s1
   • j represents the current index in string s2
   • The function returns true if we can form the remaining part of s3 starting from position i + j using characters from s1[i:] and s2[j:]

3. Base Case: When i >= m and j >= n (where m = len(s1) and n = len(s2)), we've used all characters from both strings, so we return true.

4. Recursive Cases: At each step, we calculate k = i + j, which represents our current position in s3. Then we check:

   • If i < m and s1[i] == s3[k]: We can take the character from s1. We recursively call dfs(i + 1, j) to check if the rest can form a valid interleaving. If it returns true, we return true.
   • If j < n and s2[j] == s3[k]: We can take the character from s2. We recursively call dfs(i, j + 1) to check if the rest can form a valid interleaving. If it returns true, we return true.
   • If neither condition is met, we return false.

5. Memoization: The @cache decorator automatically memoizes the results of dfs(i, j). This prevents redundant calculations when the same state (i, j) is reached through different paths, reducing time complexity from exponential to O(m × n).

Why This Works:

The algorithm explores all possible ways to interleave s1 and s2. At each position in s3, it tries to match the current character with either the current character in s1 or s2 (if they match), then recursively checks if the remaining characters can form a valid interleaving. The memoization ensures that each unique state is computed only once, making the solution efficient.

Time Complexity: O(m × n) where m and n are the lengths of s1 and s2 respectively, since we have at most m × n unique states.

Space Complexity: O(m × n) for the memoization cache plus O(m + n) for the recursion stack depth.

Example Walkthrough

Let's walk through a small example with s1 = "ab", s2 = "cd", and s3 = "acbd".

Step 1: Initial Check

• Length check: len(s1) + len(s2) = 2 + 2 = 4 = len(s3) ✓
• We can proceed with the algorithm.

Step 2: Start DFS from (0, 0)

We'll trace through the recursive calls. Each state is represented as dfs(i, j) where i is the index in s1 and j is the index in s2.

dfs(0, 0): k = 0+0 = 0, need to match s3[0] = 'a'
- s1[0] = 'a' matches s3[0] ✓ → try dfs(1, 0)
- s2[0] = 'c' doesn't match s3[0] ✗

dfs(1, 0): k = 1+0 = 1, need to match s3[1] = 'c'
- s1[1] = 'b' doesn't match s3[1] ✗
- s2[0] = 'c' matches s3[1] ✓ → try dfs(1, 1)

dfs(1, 1): k = 1+1 = 2, need to match s3[2] = 'b'
- s1[1] = 'b' matches s3[2] ✓ → try dfs(2, 1)
- s2[1] = 'd' doesn't match s3[2] ✗

dfs(2, 1): k = 2+1 = 3, need to match s3[3] = 'd'
- i = 2 >= len(s1), can't use s1
- s2[1] = 'd' matches s3[3] ✓ → try dfs(2, 2)

dfs(2, 2): Base case reached!
- i = 2 >= len(s1) = 2 ✓
- j = 2 >= len(s2) = 2 ✓
- Return true

Step 3: Backtrack with Results

The recursive calls return true all the way back:

• dfs(2, 2) returns true
• dfs(2, 1) returns true (because taking 'd' from s2 worked)
• dfs(1, 1) returns true (because taking 'b' from s1 worked)
• dfs(1, 0) returns true (because taking 'c' from s2 worked)
• dfs(0, 0) returns true (because taking 'a' from s1 worked)

Result: The function returns true, confirming that "acbd" is a valid interleaving of "ab" and "cd".

The characters were taken in this order:

• 'a' from s1 (position 0)
• 'c' from s2 (position 0)
• 'b' from s1 (position 1)
• 'd' from s2 (position 1)

This forms "acbd" while maintaining the relative order of characters from both strings.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the length of string s1 and n is the length of string s2. This is because the recursive function dfs(i, j) can have at most m × n unique states (with i ranging from 0 to m and j ranging from 0 to n). Due to the @cache decorator, each state is computed only once, and subsequent calls to the same state return the cached result immediately.

The space complexity is O(m × n). This accounts for two factors:

1. The cache storage used by the @cache decorator, which stores up to m × n states
2. The recursive call stack depth, which in the worst case can go up to O(m + n) when we traverse through all characters of either s1 or s2 before backtracking

Since O(m × n) dominates O(m + n), the overall space complexity is O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting the Length Check

One of the most common mistakes is diving straight into the recursive solution without first checking if the total length matches. This can lead to unnecessary computation or incorrect results.

Pitfall Example:

def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
    @cache
    def dfs(i, j):
        # Directly start recursion without length check
        if i >= len(s1) and j >= len(s2):
            return True
        # ... rest of the code
    return dfs(0, 0)

Why it's wrong: If len(s1) + len(s2) ≠ len(s3), the function might still return True when it reaches the end of s1 and s2, even though we haven't consumed all of s3 (or have consumed too much).

Solution: Always verify len(s1) + len(s2) == len(s3) before starting the recursion.

2. Incorrect Index Calculation for s3

Another frequent error is incorrectly tracking the position in s3 or using a separate index that can get out of sync.

Pitfall Example:

@cache
def dfs(i, j, k):  # Adding a third parameter for s3 index
    if i >= len(s1) and j >= len(s2):
        return k >= len(s3)
  
    if i < len(s1) and s1[i] == s3[k]:
        if dfs(i + 1, j, k + 1):  # Manually incrementing k
            return True
    # ... rest of the code

Why it's wrong: Adding an extra parameter increases complexity and memory usage. Since k is always equal to i + j, it's redundant and can lead to bugs if not maintained correctly.

Solution: Always calculate k = i + j within the function rather than passing it as a parameter.

3. Missing Memoization

Without memoization, the solution becomes exponentially slow for larger inputs due to repeated calculations of the same states.

Pitfall Example:

def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
    def dfs(i, j):  # No @cache decorator
        if i >= len(s1) and j >= len(s2):
            return True
        # ... rest of the code
    return dfs(0, 0)

Why it's wrong: Without memoization, the time complexity becomes O(2^(m+n)) in the worst case, causing timeout for larger inputs.

Solution: Use @cache decorator or implement manual memoization with a dictionary.

4. Incorrect Boundary Checks

Using wrong comparison operators or checking bounds after accessing the array can cause index out of range errors.

Pitfall Example:

@cache
def dfs(i, j):
    if i == len(s1) and j == len(s2):  # Using == instead of >=
        return True
  
    k = i + j
    # Checking bounds AFTER accessing the character
    if s1[i] == s3[k] and i < len(s1):  # Wrong order!
        if dfs(i + 1, j):
            return True

Why it's wrong:

• Using == instead of >= might miss the base case if indices somehow exceed the length
• Accessing s1[i] before checking i < len(s1) causes IndexError

Solution: Always check bounds before accessing array elements, and use >= for safety in base case.

5. Not Handling Empty Strings

The solution might fail or behave unexpectedly with empty strings if not properly considered.

Pitfall Example:

def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
    if not s1 and not s2 and not s3:  # Only checking if all are empty
        return True
    # ... rest of the code

Why it's wrong: This doesn't handle cases where only one or two strings are empty. For example, if s1 = "", s2 = "abc", s3 = "abc", this should return True.

Solution: The length check len(s1) + len(s2) == len(s3) naturally handles empty strings correctly, and the recursive solution works fine with empty strings as long as the length check passes.