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 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1s1 + 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:
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 <= 1000 <= s3.length <= 200s1, s2, and s3 consist of lowercase English letters.Follow up: Could you solve it using only O(s2.length) additional memory space?
The key idea in Interleaving String is to determine whether a third string s3 can be formed by merging characters from s1 and s2 while preserving the relative order of characters in each string. A brute-force approach would try all possible combinations, but this leads to exponential time.
A more efficient solution uses Dynamic Programming. Define a DP state where dp[i][j] represents whether the first i characters of s1 and the first j characters of s2 can form the first i + j characters of s3. At each step, you check if the next character in s3 matches either the next character in s1 or s2. If so, you transition from the corresponding previous state.
This approach systematically builds valid prefixes and avoids recomputation using memoization or tabulation. The DP solution runs in O(m × n) time where m and n are the lengths of s1 and s2. Space can be optimized from O(m × n) to O(n) using a rolling array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (2D DP) | O(m × n) | O(m × n) |
| Dynamic Programming (Space Optimized) | O(m × n) | O(n) |
NeetCode
This approach uses a dynamic programming table to ascertain whether the third string, s3, is an interleaving of s1 and s2. We use a 2D DP array dp[i][j] which signifies if s3[0:i+j] is an interleaving of s1[0:i] and s2[0:j]. A bottom-up approach is taken to fill this table.
Time Complexity: O(n * m), where n and m are the lengths of s1 and s2, respectively.
Space Complexity: O(n * m), required for the dp array.
1public class Solution {
2 public boolean isInterleave(String s1, String s2, String s3) {
3 int n = s1.length();This Java solution uses a 2D boolean array dp to keep track of whether it's possible to interleave to form s3. The loop structure is used to check and update cells based on previous valid paths that can form the substring up to i + j.
This recursive approach tries to construct the interleaved string by attempting to use characters from s1 and s2 to match each character of s3. To optimize, memoization is applied to avoid recalculating results for the same subproblems.
Time Complexity: O(n * m), due to memoization allowing only one calculation per subproblem.
Space Complexity: O(n * m) for the memoization table.
1using System.Collections.Generic;
public class Solution {
public bool IsInterleave(string s1, string s2, string s3) {
if (s1.Length + s2.Length != s3.Length)
return false;
return IsInterleave(s1, 0, s2, 0, s3, 0, new Dictionary<string, bool>());
}
private bool IsInterleave(string s1, int i, string s2, int j, string s3, int k, Dictionary<string, bool> memo) {
if (k == s3.Length)
return true;
string key = i + ":" + j;
if (memo.ContainsKey(key))
return memo[key];
bool ans = false;
if (i < s1.Length && s1[i] == s3[k])
ans = IsInterleave(s1, i + 1, s2, j, s3, k + 1, memo);
if (!ans && j < s2.Length && s2[j] == s3[k])
ans = IsInterleave(s1, i, s2, j + 1, s3, k + 1, memo);
memo[key] = ans;
return ans;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Interleaving String is a common medium-level dynamic programming problem that tests string manipulation and DP state transitions. Variations of this problem have appeared in interviews at top tech companies.
Yes, a recursive solution with memoization can solve the problem by exploring choices from both strings. However, pure recursion without memoization leads to exponential time complexity due to repeated subproblems.
The optimal approach uses dynamic programming. By defining a DP state that tracks whether prefixes of two strings can form a prefix of the third string, we can efficiently verify interleaving in O(m × n) time.
Dynamic programming with a 2D array or a space-optimized 1D array is most effective. It allows you to store intermediate results for combinations of prefixes from the two strings.
The C# solution uses recursion with a dictionary for memoization. It tries to match s3 by incrementally using characters from s1 and s2, storing previous results for quick returns.