Interleaving String
MediumUpdated: Aug 4, 2025
Practice on:
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 they are divided into non-empty substrings such that:
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- The interleaving is
s1 + t1 + s2 + t2 + s3 + t3 + ...ort1 + s1 + t2 + s2 + t3 + s3 + ...
Note: a + b is the concatenation of strings a and b.
To summarize: Interleaving of 2 strings is such that we break them into non-empty substring and concatenate them in the relative orders.
For eg. s1=ABC, and s2=DEF, then when we split s1 in A, B, C, they should occur in same order in new string s3. Likewise for s2.
Examples
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation:
s1: a a b c c
↓ ↓ ↓ ↓ ↓
s3: a a d b b c b c a c
↑ ↑ ↑ ↑ ↑
s2: d b b c a
Here is how we can make s3 from s1 and s2:
1. Take 'a' from s1 → "a"
2. Take 'a' from s1 → "aa"
3. Take 'd' from s2 → "aad"
4. Take 'b' from s2 → "aadb"
5. Take 'b' from s2 → "aadbb"
6. Take 'c' from s1 → "aadbb" + "c" = "aadbbcc"
7. Take 'b' from s1 → "aadbbcb"
8. Take 'c' from s2 → "aadbbcbc"
9. Take 'a' from s2 → "aadbbcbca"
10. Take 'c' from s1 → "aadbbcbcac"
Result: s3 = "aadbbcbcac" ✓
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Example 3:
Input: s1 = "", s2 = "", s3 = ""
Output: true
Solution
Method 1 - Brute Force
Intuition
Try every possible way to interleave s1 and s2 to form s3. At each step, choose either the next character from s1 or s2 if it matches the corresponding character in s3. Use backtracking to explore all possibilities.
Approach
Use recursion with three pointers (i1, i2, i3) for s1, s2, and s3. At each step, if the current character in s3 matches the next character in s1, recurse by advancing i1 and i3. Similarly, if it matches the next character in s2, recurse by advancing i2 and i3. If both match, try both options. If neither matches, backtrack.
Complexity
- ⏰ Time complexity:
O(2^(m+n)), wheremandnare the lengths ofs1ands2. Each character can be chosen from either string, leading to exponential possibilities. - 🧺 Space complexity:
O(m+n), due to the recursion stack depth.
Method 2 - Top Down DP with Memoization
Code
C++
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;
vector<vector<int>> memo(m + 1, vector<int>(n + 1, -1));
function<bool(int, int)> dfs = [&](int i, int j) {
if (i == m && j == n) return true;
if (memo[i][j] != -1) return memo[i][j];
int k = i + j;
bool res = false;
if (i < m && s1[i] == s3[k] && dfs(i + 1, j)) res = true;
if (j < n && s2[j] == s3[k] && dfs(i, j + 1)) res = true;
return memo[i][j] = res;
};
return dfs(0, 0);
}
};
Go
func isInterleave(s1, s2, s3 string) bool {
m, n := len(s1), len(s2)
if m+n != len(s3) {
return false
}
memo := make([][]int, m+1)
for i := range memo {
memo[i] = make([]int, n+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(i, j int) bool
dfs = func(i, j int) bool {
if i == m && j == n {
return true
}
if memo[i][j] != -1 {
return memo[i][j] == 1
}
k := i + j
res := false
if i < m && s1[i] == s3[k] && dfs(i+1, j) {
res = true
}
if j < n && s2[j] == s3[k] && dfs(i, j+1) {
res = true
}
if res {
memo[i][j] = 1
} else {
memo[i][j] = 0
}
return res
}
return dfs(0, 0)
}
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[][] memo = new Boolean[m + 1][n + 1];
return dfs(s1, s2, s3, 0, 0, memo);
}
private boolean dfs(String s1, String s2, String s3, int i, int j, Boolean[][] memo) {
if (i == s1.length() && j == s2.length()) return true;
if (memo[i][j] != null) return memo[i][j];
int k = i + j;
boolean res = false;
if (i < s1.length() && s1.charAt(i) == s3.charAt(k) && dfs(s1, s2, s3, i + 1, j, memo)) res = true;
if (j < s2.length() && s2.charAt(j) == s3.charAt(k) && dfs(s1, s2, s3, i, j + 1, memo)) res = true;
return memo[i][j] = res;
}
}
Kotlin
class Solution {
fun isInterleave(s1: String, s2: String, s3: String): Boolean {
val m = s1.length
val n = s2.length
if (m + n != s3.length) return false
val memo = Array(m + 1) { Array<Boolean?>(n + 1) { null } }
fun dfs(i: Int, j: Int): Boolean {
if (i == m && j == n) return true
memo[i][j]?.let { return it }
val k = i + j
var res = false
if (i < m && s1[i] == s3[k] && dfs(i + 1, j)) res = true
if (j < n && s2[j] == s3[k] && dfs(i, j + 1)) res = true
memo[i][j] = res
return res
}
return dfs(0, 0)
}
}
Python
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
memo = {}
def dfs(i, j):
if (i, j) in memo:
return memo[(i, j)]
if i == m and j == n:
return True
k = i + j
res = False
if i < m and s1[i] == s3[k] and dfs(i + 1, j):
res = True
if j < n and s2[j] == s3[k] and dfs(i, j + 1):
res = True
memo[(i, j)] = res
return res
return dfs(0, 0)
Rust
impl Solution {
pub fn is_interleave(s1: String, s2: String, s3: String) -> bool {
let m = s1.len();
let n = s2.len();
if m + n != s3.len() { return false; }
let s1 = s1.as_bytes();
let s2 = s2.as_bytes();
let s3 = s3.as_bytes();
let mut memo = vec![vec![None; n + 1]; m + 1];
fn dfs(i: usize, j: usize, s1: &[u8], s2: &[u8], s3: &[u8], memo: &mut Vec<Vec<Option<bool>>>) -> bool {
if let Some(v) = memo[i][j] { return v; }
if i == s1.len() && j == s2.len() { return true; }
let k = i + j;
let mut res = false;
if i < s1.len() && s1[i] == s3[k] && dfs(i + 1, j, s1, s2, s3, memo) { res = true; }
if j < s2.len() && s2[j] == s3[k] && dfs(i, j + 1, s1, s2, s3, memo) { res = true; }
memo[i][j] = Some(res);
res
}
dfs(0, 0, s1, s2, s3, &mut memo)
}
}
TypeScript
function isInterleave(s1: string, s2: string, s3: string): boolean {
const m = s1.length, n = s2.length;
if (m + n !== s3.length) return false;
const memo: (boolean | undefined)[][] = Array.from({ length: m + 1 }, () => Array(n + 1));
function dfs(i: number, j: number): boolean {
if (memo[i][j] !== undefined) return memo[i][j]!;
if (i === m && j === n) return true;
const k = i + j;
let res = false;
if (i < m && s1[i] === s3[k] && dfs(i + 1, j)) res = true;
if (j < n && s2[j] === s3[k] && dfs(i, j + 1)) res = true;
memo[i][j] = res;
return res;
}
return dfs(0, 0);
}
Method 3 - Bottom up DP
Intuition
Use dynamic programming to build a table dp[i][j] indicating whether s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1]. Start from the base case and fill the table iteratively.
Approach
Create a 2D DP table of size (m+1) x (n+1). Initialize dp[0][0] = True. For each cell, check if the previous state is valid and the current character matches. Fill the table row by row and return dp[m][n].
Code
C++
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;
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)
dp[i][j] = dp[i][j] || (dp[i-1][j] && s1[i-1] == s3[i+j-1]);
if (j > 0)
dp[i][j] = dp[i][j] || (dp[i][j-1] && s2[j-1] == s3[i+j-1]);
}
}
return dp[m][n];
}
};
Go
func isInterleave(s1, s2, s3 string) bool {
m, n := len(s1), len(s2)
if m+n != len(s3) {
return false
}
dp := make([][]bool, m+1)
for i := range dp {
dp[i] = make([]bool, n+1)
}
dp[0][0] = true
for i := 0; i <= m; i++ {
for j := 0; j <= n; j++ {
if i > 0 && dp[i-1][j] && s1[i-1] == s3[i+j-1] {
dp[i][j] = true
}
if j > 0 && dp[i][j-1] && s2[j-1] == s3[i+j-1] {
dp[i][j] = true
}
}
}
return dp[m][n]
}
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[][] 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)
dp[i][j] |= dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1);
if (j > 0)
dp[i][j] |= dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1);
}
}
return dp[m][n];
}
}
Kotlin
class Solution {
fun isInterleave(s1: String, s2: String, s3: String): Boolean {
val m = s1.length
val n = s2.length
if (m + n != s3.length) return false
val dp = Array(m + 1) { BooleanArray(n + 1) }
dp[0][0] = true
for (i in 0..m) {
for (j in 0..n) {
if (i > 0)
dp[i][j] = dp[i][j] || (dp[i-1][j] && s1[i-1] == s3[i+j-1])
if (j > 0)
dp[i][j] = dp[i][j] || (dp[i][j-1] && s2[j-1] == s3[i+j-1])
}
}
return dp[m][n]
}
}
Python
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
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(m + 1):
for j in range(n + 1):
if i > 0:
dp[i][j] |= dp[i-1][j] and s1[i-1] == s3[i+j-1]
if j > 0:
dp[i][j] |= dp[i][j-1] and s2[j-1] == s3[i+j-1]
return dp[m][n]
Rust
impl Solution {
pub fn is_interleave(s1: String, s2: String, s3: String) -> bool {
let m = s1.len();
let n = s2.len();
if m + n != s3.len() { return false; }
let s1 = s1.as_bytes();
let s2 = s2.as_bytes();
let s3 = s3.as_bytes();
let mut dp = vec![vec![false; n + 1]; m + 1];
dp[0][0] = true;
for i in 0..=m {
for j in 0..=n {
if i > 0 && dp[i-1][j] && s1[i-1] == s3[i+j-1] {
dp[i][j] = true;
}
if j > 0 && dp[i][j-1] && s2[j-1] == s3[i+j-1] {
dp[i][j] = true;
}
}
}
dp[m][n]
}
}
TypeScript
function isInterleave(s1: string, s2: string, s3: string): boolean {
const m = s1.length, n = s2.length;
if (m + n !== s3.length) return false;
const dp: boolean[][] = 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 && dp[i-1][j] && s1[i-1] === s3[i+j-1]) {
dp[i][j] = true;
}
if (j > 0 && dp[i][j-1] && s2[j-1] === s3[i+j-1]) {
dp[i][j] = true;
}
}
}
return dp[m][n];
}
Complexity
- ⏰ Time complexity:
O(mn), wheremandnare the lengths ofs1ands2. Each cell in the DP table is computed once. - 🧺 Space complexity:
O(mn), for the DP table.