Interleaving String

How it works

We want to check if s3 can be formed by interleaving s1 and s2 while keeping the order of characters from both strings.

A common DP idea is:

• at positions (i, j), we have used i characters from s1 and j characters from s2
• so the next character we must match in s3 is at index i + j

From this state, we can move forward in two ways:

• take s1[i] if it matches s3[i + j]
• take s2[j] if it matches s3[i + j]

The 2D DP solution stores this for every (i, j), but we can do better:

• each DP row only depends on the row below and the current row being built
• so we can reuse a single 1D array
• and instead of building a separate next array, we can update the 1D array in-place using one extra variable that tracks the “right neighbor” value

We also swap strings so that s2 is the longer one, keeping the DP array as small as possible.

Steps

1. Let m = len(s1) and n = len(s2).
2. If m + n != len(s3), return false immediately.
3. If s2 is shorter than s1, swap them so the DP array size becomes O(min(m, n)).
4. Create a boolean array dp of size n + 1:
   • dp[j] represents whether s3[i + j:] can be formed using s1[i:] and s2[j:] for the current i
5. Initialize the base case:
   • set dp[n] = true (when both suffixes are empty)
6. Iterate i from m down to 0:
   • keep a variable nextDp that represents the value to the right (dp[j + 1]) for the current row
   • initialize it as true only when i == m (bottom row base case)
7. Iterate j from n down to 0:
   • compute whether the state (i, j) is valid:
     • it is valid if taking from s1 matches and the state below (dp[j]) was valid
     • or taking from s2 matches and the state to the right (nextDp) is valid
   • write the result back into dp[j] (in-place update)
   • update nextDp to the new dp[j] for the next iteration to the left
8. After all updates, dp[0] tells whether s3 can be formed starting from the beginning of both strings.
9. Return dp[0]

Complexity

• Time complexity: O(m * n)
• Space complexity: O(min(m, n))

Where m is the length of the string s1 and n is the length of the string s2.

Things to watch for

Skipping the Length Check

A quick optimization that many solutions miss is checking if len(s1) + len(s2) == len(s3) upfront. If the lengths do not match, interleaving is impossible regardless of the characters. Skipping this check leads to unnecessary computation and can cause index out-of-bounds errors in some implementations.

Confusing Position Tracking with Three Indices

Since k = i + j always holds (where k is position in s3, i in s1, j in s2), you only need to track two indices. Some implementations incorrectly track all three independently, leading to inconsistent states or missed memoization opportunities. The key insight is that knowing positions in s1 and s2 uniquely determines the position in s3.

Greedy Character Matching

When both s1[i] and s2[j] match s3[k], you cannot greedily choose one over the other. Both branches must be explored. A common bug is to always prefer taking from s1 (or s2) when both match, which fails for cases like s1 = "a", s2 = "a", s3 = "aa" where either order works but a greedy approach might get stuck.

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
        if n < m:
            s1, s2 = s2, s1
            m, n = n, m

        dp = [False for _ in range(n + 1)]
        dp[n] = True
        for i in range(m, -1, -1):
            nextDp = True if i == m else False
            for j in range(n, -1, -1):
                res = False if j < n else nextDp
                if i < m and s1[i] == s3[i + j] and dp[j]:
                    res = True
                if j < n and s2[j] == s3[i + j] and nextDp:
                    res = True
                dp[j] = res
                nextDp = dp[j]
        return dp[0]

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size();
        if (m + n != s3.size()) return false;
        if (n < m) {
            swap(s1, s2);
            swap(m, n);
        }

        vector<bool> dp(n + 1, false);
        dp[n] = true;
        for (int i = m; i >= 0; i--) {
            bool nextDp = (i == m ? true : false);
            for (int j = n; j >= 0; j--) {
                bool res = (j < n ? false : nextDp);
                if (i < m && s1[i] == s3[i + j] && dp[j]) {
                    res = true;
                }
                if (j < n && s2[j] == s3[i + j] && nextDp) {
                    res = true;
                }
                dp[j] = res;
                nextDp = dp[j];
            }
        }
        return dp[0];
    }
};