Interleaving String — Solution in Python, Java & C++
Interleaving String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Interleaving String is a medium coding problem on strings and dynamic programming, asked in Amazon, Google, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Google, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given three strings s1, s2 and s3, return true if s3 is formed by interleaving s1 and s2.
An interleaving splits both strings into blocks and alternates them, preserving the order within each original string.
Example 1
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Example 3
Input: s1 = "", s2 = "", s3 = ""
Output: true
Constraints
0 <= s1.length, s2.length <= 15s3.length == s1.length + s2.length is required for a true answer.All strings consist of lowercase English letters.
Hints for Interleaving String
Hint 1
The lengths must add up; otherwise reject immediately.
Hint 2
Let
dp[i][j]mean the firsticharacters ofs1and the firstjofs2can interleave into the firsti + jofs3.Hint 3
The next character of
s3must come from one side or the other — that is exactly the two transitions.
How to solve Interleaving String
dp[i][j] says whether the first i characters of s1 and the first j of s2 can interleave into the first i + j of s3; the next character of s3 comes from one side or the other.
Approach
- Reject if
len(s1) + len(s2) != len(s3). - Set
dp[0][0] = true; thendp[i][j]is true ifdp[i-1][j]ands1[i-1] == s3[i+j-1], ordp[i][j-1]ands2[j-1] == s3[i+j-1]. - Return
dp[m][n].
Why it works
The last character of any interleaving prefix must be the last used character of s1 or of s2, so the two transitions cover every case and the table is exact.
Complexity
- Time —
O(m · n) - Space —
O(m · n), reducible to one row
Pitfalls
- The length check is what makes the indexing safe, and it also prunes most rejections instantly.
Reference solution
Python
def isInterleave(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 and dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]:
dp[i][j] = True
if j > 0 and dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]:
dp[i][j] = True
return dp[m][n]Java
public static 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 - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) dp[i][j] = true;
if (j > 0 && dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) dp[i][j] = true;
}
}
return dp[m][n];
}C++
bool isInterleave(string s1, string s2, string s3) {
int m = (int) s1.size(), n = (int) s2.size();
if (m + n != (int) 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 - 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];
}JavaScript
var isInterleave = function(s1, s2, s3) {
const m = s1.length, n = s2.length;
if (m + n !== s3.length) return false;
const dp = [];
for (let i = 0; i <= m; i++) dp.push(new 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];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming