# Interleaving String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/interleaving-string)
Canonical: https://scaleengineer.com/dsa/problems/interleaving-string
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Microsoft](https://scaleengineer.com/companies/microsoft), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zeta](https://scaleengineer.com/companies/zeta), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [thoughtspot](https://scaleengineer.com/companies/thoughtspot), [Nuro](https://scaleengineer.com/companies/nuro)
---
## Problem
Given strings `s1`, `s2`, and `s3`, find whether `s3` is formed by an **interleaving** of `s1` and `s2`.

An **interleaving** of two strings `s` and `t` is a configuration where `s` and `t` are divided into `n` and `m` substrings respectively, such that:

* `s = s1 + s2 + ... + sn`
* `t = t1 + t2 + ... + tm`
* `|n - m| <= 1`
* The **interleaving** is `s1 + t1 + s2 + t2 + s3 + t3 + ...` or `t1 + s1 + t2 + s2 + t3 + s3 + ...`

**Note:** `a + b` is the concatenation of strings `a` and `b`.

**Example 1:**

![](https://assets.glich.co/dsa/interleaving-string/image0.jpg) 

**Input:** s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
**Output:** true
**Explanation:** One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".
Since s3 can be obtained by interleaving s1 and s2, we return true.

**Example 2:**

**Input:** s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
**Output:** false
**Explanation:** Notice how it is impossible to interleave s2 with any other string to obtain s3.

**Example 3:**

**Input:** s1 = "", s2 = "", s3 = ""
**Output:** true

**Constraints:**

* `0 <= s1.length, s2.length <= 100`
* `0 <= s3.length <= 200`
* `s1`, `s2`, and `s3` consist of lowercase English letters.

**Follow up:** Could you solve it using only `O(s2.length)` additional memory space?

# Approaches
## Brute-Force Recursion
This approach uses a simple recursive function to explore all possible ways of forming `s3` by picking characters from `s1` and `s2`. It directly models the decision process: at each character of `s3`, we decide whether to match it with the current character of `s1` or `s2`. If a character in `s3` matches both, we explore both possibilities recursively.
**Time:** O(2^(m+n)) · **Space:** O(m + n)
**Pros:** Simple to understand and implement.; Directly translates the problem definition into code.
**Cons:** Extremely inefficient due to a large number of redundant computations for the same subproblems (i.e., the same `i` and `j` values are computed multiple times through different recursive paths).; Will likely result in a 'Time Limit Exceeded' error on most online judges for non-trivial inputs.
### Explanation
The method involves a helper function that takes two pointers, `i` for `s1` and `j` for `s2`, indicating the number of characters already used from each string. The current character to be matched in `s3` is at index `k = i + j`.

If the current character of `s3` matches the character at `s1[i]`, we recursively call the function with `i+1`. If it matches `s2[j]`, we recursively call with `j+1`. If it matches both, we try both paths and return `true` if either path leads to a solution. The recursion stops when we have successfully used all characters from both `s1` and `s2`.

```java
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        return check(s1, s2, s3, 0, 0);
    }

    private boolean check(String s1, String s2, String s3, int i, int j) {
        // Base case: if we have reached the end of all strings
        if (i == s1.length() && j == s2.length()) {
            return true;
        }

        boolean match1 = false;
        if (i < s1.length() && s1.charAt(i) == s3.charAt(i + j)) {
            match1 = check(s1, s2, s3, i + 1, j);
        }

        // If the first path was successful, no need to check the second
        if (match1) {
            return true;
        }

        boolean match2 = false;
        if (j < s2.length() && s2.charAt(j) == s3.charAt(i + j)) {
            match2 = check(s1, s2, s3, i, j + 1);
        }

        return match2;
    }
}
```
### Algorithm
- The core idea is to use a recursive function, say `check(i, j)`, which determines if the rest of `s3` (from index `i+j`) can be formed by the rest of `s1` (from index `i`) and the rest of `s2` (from index `j`).
- First, perform a preliminary check: if `s1.length() + s2.length() != s3.length()`, it's impossible to form `s3`, so return `false`.
- **Base Case:** If we have successfully traversed all of `s1` and `s2` (i.e., `i == s1.length()` and `j == s2.length()`), it means we have successfully formed `s3`. Return `true`.
- **Recursive Step:** At the current state `(i, j)`, we are trying to match `s3.charAt(i+j)`.
  - If `s1.charAt(i)` matches `s3.charAt(i+j)`, we make a recursive call `check(i + 1, j)`. If this call returns `true`, we have found a valid interleaving.
  - If `s2.charAt(j)` matches `s3.charAt(i+j)`, we make a recursive call `check(i, j + 1)`. If this call returns `true`, we have also found a valid interleaving.
  - The result for `check(i, j)` is `true` if either of the possible recursive calls returns `true`.
  - If neither character matches or if the subsequent recursive calls return `false`, this path is invalid.

## Recursion with Memoization (Top-Down DP)
The brute-force approach suffers from re-calculating the same subproblems multiple times. We can optimize this by using memoization, a top-down dynamic programming technique. We store the result of each unique state `(i, j)` in a 2D array. When the recursive function is called for a state that has already been computed, we simply return the stored result instead of re-computing it.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Drastically improves time complexity by eliminating redundant computations.; Guaranteed to run in polynomial time.; Relatively easy to convert from the brute-force recursive solution.
**Cons:** Requires O(m*n) extra space for the memoization table.; While much faster, it still uses recursion, which might have a slight overhead compared to a purely iterative solution.
### Explanation
We enhance the recursive solution by adding a 2D array, `memo`, to cache the results. `memo[i][j]` will store whether an interleaving is possible for `s1`'s suffix starting at `i` and `s2`'s suffix starting at `j`. We can use an integer array where `1` means true, `0` means false, and `-1` (or another sentinel value) means not computed.

This avoids the exponential explosion of recursive calls by ensuring that each subproblem `check(i, j)` is solved only once. The time complexity is reduced to the number of states multiplied by the work done per state, which is constant.

```java
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        // -1: not computed, 0: false, 1: true
        int[][] memo = new int[s1.length() + 1][s2.length() + 1];
        for (int[] row : memo) {
            java.util.Arrays.fill(row, -1);
        }
        return check(s1, s2, s3, 0, 0, memo) == 1;
    }

    private int check(String s1, String s2, String s3, int i, int j, int[][] memo) {
        if (i == s1.length() && j == s2.length()) {
            return 1;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        boolean match1 = false;
        if (i < s1.length() && s1.charAt(i) == s3.charAt(i + j)) {
            if (check(s1, s2, s3, i + 1, j, memo) == 1) {
                match1 = true;
            }
        }

        if (match1) {
            memo[i][j] = 1;
            return 1;
        }

        boolean match2 = false;
        if (j < s2.length() && s2.charAt(j) == s3.charAt(i + j)) {
            if (check(s1, s2, s3, i, j + 1, memo) == 1) {
                match2 = true;
            }
        }

        memo[i][j] = match2 ? 1 : 0;
        return memo[i][j];
    }
}
```
### Algorithm
- First, check if `s1.length() + s2.length() != s3.length()`. If not, return `false`.
- Create a 2D memoization table, `memo`, of size `(s1.length() + 1) x (s2.length() + 1)` to store the results of subproblems. Initialize it with a value indicating that the state has not been computed (e.g., -1 or null).
- Use a recursive helper function `check(i, j)` as in the brute-force approach.
- **Memoization Check:** Before computing `check(i, j)`, check if `memo[i][j]` has already been computed. If so, return the stored value.
- **Recursive Step:** If the result is not in the memo table, compute it as in the brute-force approach.
- **Store Result:** Before returning the computed result, store it in `memo[i][j]` for future use.

## 2D Dynamic Programming
This approach converts the top-down memoized recursion into a bottom-up iterative solution. We use a 2D DP table where `dp[i][j]` represents whether the first `i` characters of `s1` and the first `j` characters of `s2` can form an interleaving of the first `i+j` characters of `s3`. We fill this table iteratively, starting from the base case `dp[0][0]`, until we compute the final answer `dp[s1.length()][s2.length()]`.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Avoids recursion and potential stack overflow issues.; Often slightly more performant than memoization due to no recursion overhead.; The logic is systematic and easy to follow.
**Cons:** Requires O(m*n) space, which might be large for the given constraints and is not the most optimal solution.
### Explanation
The state `dp[i][j]` holds a boolean value. The table is of size `(m+1) x (n+1)`. We build the solution from smaller subproblems to larger ones.

`dp[i][j]` is true if either of these conditions holds:
1. The `i`-th character of `s1` (i.e., `s1[i-1]`) matches the `(i+j)`-th character of `s3` (i.e., `s3[i+j-1]`), AND the subproblem `dp[i-1][j]` is true.
2. The `j`-th character of `s2` (i.e., `s2[j-1]`) matches the `(i+j)`-th character of `s3` (i.e., `s3[i+j-1]`), AND the subproblem `dp[i][j-1]` is true.

By filling the table row by row or column by column, we can compute the final result at `dp[m][n]`.

```java
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }

        boolean[][] dp = new boolean[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i - 1);
                } else {
                    dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) ||
                               (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
                }
            }
        }

        return dp[m][n];
    }
}
```
### Algorithm
- First, check the length constraint: `s1.length() + s2.length() != s3.length()`.
- Create a 2D boolean DP table `dp` of size `(m+1) x (n+1)`, where `m=s1.length()` and `n=s2.length()`.
- `dp[i][j]` will be `true` if `s3`'s prefix of length `i+j` is an interleaving of `s1`'s prefix of length `i` and `s2`'s prefix of length `j`.
- **Base Case:** `dp[0][0] = true` (two empty strings form an empty string).
- **Fill First Row:** `dp[0][j]` is `true` if `s2`'s prefix matches `s3`'s prefix. `dp[0][j] = dp[0][j-1] && s2.charAt(j-1) == s3.charAt(j-1)`.
- **Fill First Column:** `dp[i][0]` is `true` if `s1`'s prefix matches `s3`'s prefix. `dp[i][0] = dp[i-1][0] && s1.charAt(i-1) == s3.charAt(i-1)`.
- **Fill the Rest:** For `dp[i][j]`, check the character `s3.charAt(i+j-1)`.
  - If it matches `s1.charAt(i-1)`, we can potentially form the string if `dp[i-1][j]` is true.
  - If it matches `s2.charAt(j-1)`, we can potentially form the string if `dp[i][j-1]` is true.
  - The transition is: `dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)) || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1))`.
- The final answer is `dp[m][n]`.

## 1D Dynamic Programming (Space Optimized)
This is the most optimized approach, addressing the follow-up question. By observing the 2D DP transition `dp[i][j] = f(dp[i-1][j], dp[i][j-1])`, we see that to compute the current row `i` of the DP table, we only need the values from the previous row `i-1`. This allows us to reduce the space complexity from O(m*n) to O(n) (or O(min(m,n))) by using only a single 1D array to store the previous row's results while computing the current row.
**Time:** O(m * n) · **Space:** O(n)
**Pros:** Optimal space complexity, using only O(n) additional space, where n is the length of the shorter string.; Maintains the efficient O(m*n) time complexity.; Directly answers the follow-up question in the problem description.
**Cons:** The logic for updating the 1D array in place can be slightly more complex to reason about compared to the 2D DP approach.
### Explanation
We can optimize the 2D DP solution's space by using a 1D array, say `dp`, of size `n+1` where `n` is the length of `s2`. `dp[j]` will store the result for `dp[i][j]`. As we iterate through `i` (from 1 to `m`), we update this `dp` array. For each `i`, the new `dp[j]` is calculated based on the old `dp[j]` (which corresponds to `dp[i-1][j]`) and the new `dp[j-1]` (which corresponds to `dp[i][j-1]`). This way, we effectively simulate filling the 2D table but only ever store one row at a time.

```java
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }

        // To optimize space, we want the 1D array to be of the smaller size.
        if (m < n) {
            return isInterleave(s2, s1, s3);
        }

        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        // Initialize first row (i=0)
        for (int j = 1; j <= n; j++) {
            dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }

        // Fill the rest of the rows
        for (int i = 1; i <= m; i++) {
            // Update first column element for current row i
            dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                // dp[j] is from previous row (i-1), dp[j-1] is from current row (i)
                dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) ||
                        (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }

        return dp[n];
    }
}
```
### Algorithm
- First, check the length constraint. If `s1.length() + s2.length() != s3.length()`, return `false`.
- To optimize space, we can ensure `s2` is the shorter string by swapping `s1` and `s2` if needed.
- Create a 1D boolean DP array `dp` of size `(s2.length() + 1)`.
- `dp[j]` will correspond to `dp[i][j]` in the 2D version. The outer loop will iterate through `i` (for `s1`) and the inner loop through `j` (for `s2`).
- **Initialization (for i=0):**
  - `dp[0] = true`.
  - For `j` from 1 to `n`, `dp[j] = dp[j-1] && s2.charAt(j-1) == s3.charAt(j-1)`.
- **Main Loop:** Iterate `i` from 1 to `m`.
  - First, update `dp[0]`: `dp[0] = dp[0] && s1.charAt(i-1) == s3.charAt(i-1)`.
  - Then, iterate `j` from 1 to `n`.
  - The update rule for `dp[j]` becomes: `dp[j] = (dp[j] && s1.charAt(i-1) == s3.charAt(i+j-1)) || (dp[j-1] && s2.charAt(j-1) == s3.charAt(i+j-1))`.
  - Here, `dp[j]` on the right side refers to the value from the previous row (`i-1`), and `dp[j-1]` refers to the already updated value in the current row (`i`).
- The final answer is the last element of the `dp` array, `dp[n]`.

# Solutions
### CSharp

```csharp
public class Solution {
    public bool IsInterleave(string s1, string s2, string s3) {
        int m = s1.Length, n = s2.Length;
        if (m + n != s3.Length) {
            return false;
        }
        bool[] f = new bool[n + 1];
        f[0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                int k = i + j - 1;
                if (i > 0) {
                    f[j] &= s1[i - 1] == s3[k];
                }
                if (j > 0) {
                    f[j] |= (f[j - 1] & s2[j - 1] == s3[k]);
                }
            }
        }
        return f[n];
    }
}
```

### Java

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

### CPP

```cpp
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;
    }
    bool f[n + 1];
    memset(f, false, sizeof(f));
    f[0] = true;
    for (int i = 0; i <= m; ++i) {
      for (int j = 0; j <= n; ++j) {
        int k = i + j - 1;
        if (i) {
          f[j] &= s1[i - 1] == s3[k];
        }
        if (j) {
          f[j] |= (s2[j - 1] == s3[k] && f[j - 1]);
        }
      }
    }
    return f[n];
  }
};

```

### Python

```python
# 2-d 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 ( 1 , len ( s1 ) + 1 ): dp [ i ][ 0 ] = s1 [ i - 1 ] == s3 [ i - 1 ] and dp [ i - 1 ][ 0 ] for i in range ( 1 , len ( s2 ) + 1 ): dp [ 0 ][ i ] = s2 [ i - 1 ] == s3 [ i - 1 ] and dp [ 0 ][ i - 1 ] # fill in dp array for i in range ( 1 , len ( s1 ) + 1 ): for j in range ( 1 , len ( s2 ) + 1 ): with_s1 = s1 [ i - 1 ] == s3 [ i + j - 1 ] and dp [ i - 1 ][ j ] with_s2 = s2 [ j - 1 ] == s3 [ i + j - 1 ] and dp [ i ][ j - 1 ] dp [ i ][ j ] = with_s1 or with_s2 return dp [ - 1 ][ - 1 ] ############ # 1-d 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 f = [ True ] + [ False ] * n for i in range ( m + 1 ): for j in range ( n + 1 ): k = i + j - 1 if i : f [ j ] &= s1 [ i - 1 ] == s3 [ k ] if j : f [ j ] |= f [ j - 1 ] and s2 [ j - 1 ] == s3 [ k ] return f [ n ] ########### class Solution : # dfs def isInterleave ( self , s1 : str , s2 : str , s3 : str ) -> bool : m , n = len ( s1 ), len ( s2 ) if m + n != len ( s3 ): return False @ cache def dfs ( i , j ): if i == m and j == n : return True return ( ( i < m and s1 [ i ] == s3 [ i + j ] and dfs ( i + 1 , j ) ) or ( j < n and s2 [ j ] == s3 [ i + j ] and dfs ( i , j + 1 ) ) ) return dfs ( 0 , 0 )
```