Scale Engineer

Interleaving String

Med
#0097Time: O(2^(m+n))Space: O(m + n)12 companies
Patterns
Dynamic Programming
Data structures
String
Companies
AmazonAppleGoldman SachsMicrosoft

Prompt

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 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • The interleaving is s1 + 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 <= 100
  • 0 <= s3.length <= 200
  • s1, s2, and s3 consist of lowercase English letters.

 

Follow up: Could you solve it using only O(s2.length) additional memory space?

Approaches

4 approaches with complexity analysis and trade-offs.

This approach uses a simple recursive function to explore all possible ways of forming s3 by picking characters from s1 and s2. It directly models the decision process: at each character of s3, we decide whether to match it with the current character of s1 or s2. If a character in s3 matches both, we explore both possibilities recursively.

Algorithm

  • The core idea is to use a recursive function, say check(i, j), which determines if the rest of s3 (from index i+j) can be formed by the rest of s1 (from index i) and the rest of s2 (from index j).
  • First, perform a preliminary check: if s1.length() + s2.length() != s3.length(), it's impossible to form s3, so return false.
  • Base Case: If we have successfully traversed all of s1 and s2 (i.e., i == s1.length() and j == s2.length()), it means we have successfully formed s3. Return true.
  • Recursive Step: At the current state (i, j), we are trying to match s3.charAt(i+j).
    • If s1.charAt(i) matches s3.charAt(i+j), we make a recursive call check(i + 1, j). If this call returns true, we have found a valid interleaving.
    • If s2.charAt(j) matches s3.charAt(i+j), we make a recursive call check(i, j + 1). If this call returns true, we have also found a valid interleaving.
    • The result for check(i, j) is true if either of the possible recursive calls returns true.
    • If neither character matches or if the subsequent recursive calls return false, this path is invalid.

Walkthrough

The method involves a helper function that takes two pointers, i for s1 and j for s2, indicating the number of characters already used from each string. The current character to be matched in s3 is at index k = i + j.

If the current character of s3 matches the character at s1[i], we recursively call the function with i+1. If it matches s2[j], we recursively call with j+1. If it matches both, we try both paths and return true if either path leads to a solution. The recursion stops when we have successfully used all characters from both s1 and s2.

public class Solution {    public boolean isInterleave(String s1, String s2, String s3) {        if (s1.length() + s2.length() != s3.length()) {            return false;        }        return check(s1, s2, s3, 0, 0);    }     private boolean check(String s1, String s2, String s3, int i, int j) {        // Base case: if we have reached the end of all strings        if (i == s1.length() && j == s2.length()) {            return true;        }         boolean match1 = false;        if (i < s1.length() && s1.charAt(i) == s3.charAt(i + j)) {            match1 = check(s1, s2, s3, i + 1, j);        }         // If the first path was successful, no need to check the second        if (match1) {            return true;        }         boolean match2 = false;        if (j < s2.length() && s2.charAt(j) == s3.charAt(i + j)) {            match2 = check(s1, s2, s3, i, j + 1);        }         return match2;    }}

Complexity

Time

O(2^(m+n))

Space

O(m + n)

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly translates the problem definition into code.

Cons

  • Extremely inefficient due to a large number of redundant computations for the same subproblems (i.e., the same i and j values are computed multiple times through different recursive paths).

  • Will likely result in a 'Time Limit Exceeded' error on most online judges for non-trivial inputs.

Solutions

public class Solution {    public bool IsInterleave(string s1, string s2, string s3) {        int m = s1.Length, n = s2.Length;        if (m + n != s3.Length) {            return false;        }        bool[] f = new bool[n + 1];        f[0] = true;        for (int i = 0; i <= m; ++i) {            for (int j = 0; j <= n; ++j) {                int k = i + j - 1;                if (i > 0) {                    f[j] &= s1[i - 1] == s3[k];                }                if (j > 0) {                    f[j] |= (f[j - 1] & s2[j - 1] == s3[k]);                }            }        }        return f[n];    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem