Log inSign up
mediumLeetCodeNot Started

Interleaving String

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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 = s_1 + s_2 + \dots + s_n - t = t_1 + t_2 + \dots + t_m - |n - m| <= 1 - The interleaving is s_1 + t_1 + s_2 + t_2 + \dots or t_1 + s_1 + t_2 + s_2 + \dots

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 "aa" + "bc" + "c" - Split s2 into "dbbc" + "a" - Interleaving: "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".

### 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 <= 100
  • 0 <= s3.length <= 200
  • s1, s2, and s3 consist of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model two-string interleaving as a path existence problem on a grid.
  • Derive the matching recurrence from top and left neighbors.
  • Optimize matrix storage to a single 1D boolean row.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Checking if target string is an order-preserving weave of two source strings.
  • Character length conservation: |s1| + |s2| == |s3|.

Algorithmic Decision Tree:

  • If lengths don't add up -> return false.
  • 2D boolean grid where moving right consumes s2, moving down consumes s1.

Connected Patterns:

Edit DistanceLongest Common SubsequenceRegular Expression Matching

1. Recursive Branching Search

Intuition

At each step, check if the current character of s3 can be taken from s1, s2, or both, and recurse.

Algorithm

  1. If s1.length + s2.length != s3.length, return false.
  2. Define dfs(i, j, k).
  3. If k == s3.length, return true.
  4. If i < s1.length and s1[i] == s3[k]: if dfs(i + 1, j, k + 1) returns true, return true.
  5. If j < s2.length and s2[j] == s3[k]: if dfs(i, j + 1, k + 1) returns true, return true.
  6. Return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4using namespace std;
5
6bool dfs(int i, int j, int k, const string& s1, const string& s2, const string& s3) {
7 if (k == (int)s3.length()) return true;
8
9 if (i < (int)s1.length() && s1[i] == s3[k]) {
10 if (dfs(i + 1, j, k + 1, s1, s2, s3)) return true;
11 }
12 if (j < (int)s2.length() && s2[j] == s3[k]) {
13 if (dfs(i, j + 1, k + 1, s1, s2, s3)) return true;
14 }
15 return false;
16}
17
18bool isInterleaveRec(string s1, string s2, string s3) {
19 if (s1.length() + s2.length() != s3.length()) return false;
20 return dfs(0, 0, 0, s1, s2, s3);
21}
22
23int main() {
24 string s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac";
25 cout << "Is Interleave (Recursive): " << (isInterleaveRec(s1, s2, s3) ? "true" : "false") << endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(2^(|s1| + |s2|))
  • Space complexity: O(|s1| + |s2|) call stack

2. 2D Dynamic Programming Tabulation

Intuition

Build boolean table dp[m + 1][n + 1] where dp[i][j] is whether s1[0..i-1] and s2[0..j-1] interleave to form s3[0..i+j-1].

Algorithm

  1. If s1.length + s2.length != s3.length, return false.
  2. Create dp of size (m + 1) x (n + 1) filled with false.
  3. dp[0][0] = true.
  4. Fill base column: dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1].
  5. Fill base row: dp[0][j] = dp[0][j - 1] && s2[j - 1] == s3[j - 1].
  6. For i = 1 to m:
  7. For j = 1 to n:
  8. k = i + j - 1
  9. dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[k]) || (dp[i][j - 1] && s2[j - 1] == s3[k])
  10. Return dp[m][n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7bool isInterleave2D(string s1, string s2, string s3) {
8 int m = s1.length(), n = s2.length();
9 if (m + n != (int)s3.length()) return false;
10
11 vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
12 dp[0][0] = true;
13
14 for (int i = 1; i <= m; i++) {
15 dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]);
16 }
17 for (int j = 1; j <= n; j++) {
18 dp[0][j] = dp[0][j - 1] && (s2[j - 1] == s3[j - 1]);
19 }
20
21 for (int i = 1; i <= m; i++) {
22 for (int j = 1; j <= n; j++) {
23 int k = i + j - 1;
24 dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[k]) ||
25 (dp[i][j - 1] && s2[j - 1] == s3[k]);
26 }
27 }
28 return dp[m][n];
29}
30
31int main() {
32 string s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac";
33 cout << "Is Interleave (2D DP): " << (isInterleave2D(s1, s2, s3) ? "true" : "false") << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

3. 1D Array Space-Optimized DP

Intuition

Maintain a single boolean array dp of size |s2| + 1. Update in place row by row.

Algorithm

  1. If s1.length + s2.length != s3.length, return false.
  2. Initialize dp of size n + 1 filled with false.
  3. dp[0] = true.
  4. Fill base row: for j = 1 to n: dp[j] = dp[j - 1] && s2[j - 1] == s3[j - 1].
  5. For i = 1 to m:
  6. dp[0] = dp[0] && s1[i - 1] == s3[i - 1]
  7. For j = 1 to n:
  8. k = i + j - 1
  9. dp[j] = (dp[j] && s1[i - 1] == s3[k]) || (dp[j - 1] && s2[j - 1] == s3[k])
  10. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7bool isInterleaveOptimal(string s1, string s2, string s3) {
8 int m = s1.length(), n = s2.length();
9 if (m + n != (int)s3.length()) return false;
10
11 vector<bool> dp(n + 1, false);
12 dp[0] = true;
13
14 for (int j = 1; j <= n; j++) {
15 dp[j] = dp[j - 1] && (s2[j - 1] == s3[j - 1]);
16 }
17
18 for (int i = 1; i <= m; i++) {
19 dp[0] = dp[0] && (s1[i - 1] == s3[i - 1]);
20 for (int j = 1; j <= n; j++) {
21 int k = i + j - 1;
22 dp[j] = (dp[j] && s1[i - 1] == s3[k]) ||
23 (dp[j - 1] && s2[j - 1] == s3[k]);
24 }
25 }
26 return dp[n];
27}
28
29int main() {
30 string s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac";
31 cout << "Is Interleave (Optimal 1D DP): " << (isInterleaveOptimal(s1, s2, s3) ? "true" : "false") << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(n) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive BranchingO(2^(m + n))O(m + n)Exhaustive branching over matching s1 or s2.Overlapping prefixes
2.2D TabulationO(m * n)O(m * n)Boolean matrix path reachability.Matrix allocation
3.1D Row TabulationOptimalO(m * n)O(n)Single 1D boolean row updated in place.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using greedy matching: If both s1[i] and s2[j] match s3[k], picking one greedily can lead to a dead end while the other leads to a valid interleaving.

Pitfall 2:

Forgetting to check |s1| + |s2| == |s3| upfront.

Crucial Edge Cases to Validate:

  • All empty strings: Output is true.
  • One source string empty: Output is true if other source equals s3.
  • Lengths do not match: Output is false immediately.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain why greedy fails: give the counterexample s1=a, s2=b, s3=ba where picking s1 first fails. Then transition directly to the 2D path reachability grid.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the length condition |s1| + |s2| == |s3| an absolute requirement for an interleaving string?

Back to DSA Sheet