# Interleaving String

- **Canonical ID**: `interleaving-string`
- **Canonical URL**: https://dsacheatsheet.com/problems/interleaving-string
- **Difficulty**: medium
- **Patterns**: 2D DP, Strings
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/interleaving-string/

## 1. Core Invariant / The Trick

Check `len(s1) + len(s2) == len(s3)` first. State `(i, j)` tracks whether `s1[:i]` and `s2[:j]` interleave to form `s3[:i + j]`. Rolling 1D row: `dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or (dp[j-1] and s2[j-1] == s3[i+j-1])`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(M * N)`
- **Space Complexity**: `O(min(M, N))`
- **Proof**: Rolling 1D boolean array computes reachability across the M×N prefix grid with zero backtracking exponential blowup.

## 3. Minimal Idiomatic Code

### Python
```python
def isInterleave(s1: str, s2: str, s3: str) -> bool:
    if len(s1) + len(s2) != len(s3):
        return False
    if len(s1) < len(s2):
        s1, s2 = s2, s1
    dp = [False] * (len(s2) + 1)
    dp[0] = True
    for j in range(1, len(s2) + 1):
        dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]
    for i in range(1, len(s1) + 1):
        dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
        for j in range(1, len(s2) + 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[-1]
```

### TypeScript
```typescript
export function isInterleave(s1: string, s2: string, s3: string): boolean {
  if (s1.length + s2.length !== s3.length) return false;
  if (s1.length < s2.length) [s1, s2] = [s2, s1];
  const dp = new Array(s2.length + 1).fill(false);
  dp[0] = true;
  for (let j = 1; j <= s2.length; j++) dp[j] = dp[j - 1] && s2[j - 1] === s3[j - 1];
  for (let i = 1; i <= s1.length; i++) {
    dp[0] = dp[0] && s1[i - 1] === s3[i - 1];
    for (let j = 1; j <= s2.length; j++) {
      dp[j] = (dp[j] && s1[i - 1] === s3[i + j - 1]) || (dp[j - 1] && s2[j - 1] === s3[i + j - 1]);
    }
  }
  return dp[s2.length];
}
```

### C++
```cpp
bool isInterleave(string s1, string s2, string s3) {
    if (s1.size() + s2.size() != s3.size()) return false;
    if (s1.size() < s2.size()) swap(s1, s2);
    vector<bool> dp(s2.size() + 1, false);
    dp[0] = true;
    for (size_t j = 1; j <= s2.size(); ++j) dp[j] = dp[j - 1] && s2[j - 1] == s3[j - 1];
    for (size_t i = 1; i <= s1.size(); ++i) {
        dp[0] = dp[0] && s1[i - 1] == s3[i - 1];
        for (size_t j = 1; j <= s2.size(); ++j)
            dp[j] = (dp[j] && s1[i - 1] == s3[i + j - 1]) || (dp[j - 1] && s2[j - 1] == s3[i + j - 1]);
    }
    return dp.back();
}
```

### Java
```java
boolean isInterleave(String s1, String s2, String s3) {
    if (s1.length() + s2.length() != s3.length()) return false;
    if (s1.length() < s2.length()) { String t = s1; s1 = s2; s2 = t; }
    boolean[] dp = new boolean[s2.length() + 1];
    dp[0] = true;
    for (int j = 1; j <= s2.length(); j++) dp[j] = dp[j-1] && s2.charAt(j-1) == s3.charAt(j-1);
    for (int i = 1; i <= s1.length(); i++) {
        dp[0] = dp[0] && s1.charAt(i-1) == s3.charAt(i-1);
        for (int j = 1; j <= s2.length(); j++)
            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[s2.length()];
}
```

### Go
```go
func isInterleave(s1, s2, s3 string) bool {
    if len(s1)+len(s2) != len(s3) { return false }
    if len(s1) < len(s2) { s1, s2 = s2, s1 }
    dp := make([]bool, len(s2)+1)
    dp[0] = true
    for j := 1; j <= len(s2); j++ { dp[j] = dp[j-1] && s2[j-1] == s3[j-1] }
    for i := 1; i <= len(s1); i++ {
        dp[0] = dp[0] && s1[i-1] == s3[i-1]
        for j := 1; j <= len(s2); j++ {
            dp[j] = (dp[j] && s1[i-1] == s3[i+j-1]) || (dp[j-1] && s2[j-1] == s3[i+j-1])
        }
    }
    return dp[len(s2)]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Skipping length guard `len(s1) + len(s2) != len(s3)` either crashes indexing or accepts trailing leftover characters.
- Forgetting `dp[0]` updates during row transitions (row `i > 0` column `0` requires `dp[0] and s1[i-1] == s3[i-1]`).

### Follow-ups
- Distinct Subsequences uses the exact same 1D counting structure on `(s, t)`.