Problem Description

Given three strings s1, s2, and s3, determine if s3 is formed by an interleaving of s1 and s2. An interleaving of two strings s1 and s2 is a string that contains all the characters of s1 and s2 exactly once, keeping the order of characters from each string.

• You may not reorder the characters within s1 or s2.
• At each step, you can take the current character from either s1 or s2 (if available), and append it to the result.
• All characters from s1 and s2 must be used exactly once to form s3.
• Return true if s3 is a valid interleaving, false otherwise.

Example:
s1 = "abc", s2 = "def", s3 = "adbcef" → true

Thought Process

To solve this problem, we first recognize that we need to check if we can build s3 by choosing characters from s1 and s2 in their respective orders. A brute-force solution would try all possible ways to interleave s1 and s2, but this would be very slow for longer strings.

We realize that at each position in s3, we have two choices: take the next character from s1 (if it matches), or from s2 (if it matches). This is similar to exploring a binary tree of decisions. However, many subproblems will be repeated, so we can use dynamic programming (DP) or memoization to avoid redundant computations.

The key insight is that the problem can be broken down into checking if prefixes of s1 and s2 can form a prefix of s3.

Solution Approach

We use dynamic programming to efficiently solve the interleaving string problem. Here’s a step-by-step explanation:

1. Check Lengths: If len(s1) + len(s2) != len(s3), return false immediately, because we can't use all characters exactly once.
2. DP Table: Create a 2D boolean table dp where dp[i][j] is true if s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1].
3. Base Case: dp[0][0] = True (empty strings interleave to form an empty string).
4. Filling the Table:
   • For each i (from 0 to len(s1)) and j (from 0 to len(s2)):
   • If i > 0 and s1[i-1] == s3[i+j-1], set dp[i][j] |= dp[i-1][j].
   • If j > 0 and s2[j-1] == s3[i+j-1], set dp[i][j] |= dp[i][j-1].
5. Result: dp[len(s1)][len(s2)] tells us whether s3 can be formed by interleaving s1 and s2.

We use a DP table because it lets us efficiently cache the results of subproblems, avoiding redundant calculations and ensuring each state is only computed once.

Example Walkthrough

Let's take s1 = "abc", s2 = "def", s3 = "adbcef".

1. Check lengths: 3 + 3 = 6 matches len(s3).
2. Build DP Table:
   • dp[0][0] = True (empty strings).
   • dp[1][0] = True if s1[0] == s3[0] ('a' == 'a').
   • dp[1][1]: Can we use s1[0] and s2[0] to form s3[0:2] ("ad")?
   • Continue filling: At each step, check if the next character of s1 or s2 matches the next character in s3, and update dp accordingly.
3. Final Check: dp[3][3] will be True, as we can interleave "abc" and "def" to get "adbcef".

Time and Space Complexity

Brute-force: Without memoization, the number of ways to interleave is exponential, specifically O(2^{m+n}) where m and n are the lengths of s1 and s2.

Optimized (DP):

• Time Complexity: O(m \times n) because we fill a table with m+1 rows and n+1 columns, and each cell is computed in constant time.
• Space Complexity: O(m \times n) for the DP table. This can be reduced to O(n) using a rolling array, since only the previous row is needed at each step.

Summary

The Interleaving String problem is a classic example of using dynamic programming to efficiently solve a problem that would otherwise require exponential time. By breaking the problem into subproblems and caching results, we avoid redundant work. The DP approach is intuitive: at each step, we check if the current character in s3 can be matched by advancing in s1 or s2, and build up the solution from the smallest prefixes. This method is efficient and robust, making it suitable for large inputs.

Code Implementation

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
        dp[0][0] = True
        for i in range(len(s1) + 1):
            for j in range(len(s2) + 1):
                if i > 0 and s1[i - 1] == s3[i + j - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
                if j > 0 and s2[j - 1] == s3[i + j - 1]:
                    dp[i][j] = dp[i][j] or dp[i][j - 1]
        return dp[len(s1)][len(s2)]
      

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        int m = s1.length(), n = s2.length();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                if (i > 0 && s1[i - 1] == s3[i + j - 1])
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                if (j > 0 && s2[j - 1] == s3[i + j - 1])
                    dp[i][j] = dp[i][j] || dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};
      

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        int m = s1.length(), n = s2.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i > 0 && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                if (j > 0 && s2.charAt(j - 1) == s3.charAt(i + j - 1))
                    dp[i][j] = dp[i][j] || dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
}
      

var isInterleave = function(s1, s2, s3) {
    if (s1.length + s2.length !== s3.length) return false;
    const m = s1.length, n = s2.length;
    const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(false));
    dp[0][0] = true;
    for (let i = 0; i <= m; i++) {
        for (let j = 0; j <= n; j++) {
            if (i > 0 && s1[i - 1] === s3[i + j - 1])
                dp[i][j] = dp[i][j] || dp[i - 1][j];
            if (j > 0 && s2[j - 1] === s3[i + j - 1])
                dp[i][j] = dp[i][j] || dp[i][j - 1];
        }
    }
    return dp[m][n];
};