97. Interleaving String

Problem Description

Given three strings s1, s2, and s3, we need to determine if s3 can be constructed by interleaving characters from s1 and s2. The interleaving of s1 and s2 should create a sequence where characters from s1 and s2 are alternated, but maintain their relative order from the original strings. There can be more than one character from either string coming in sequence, but overall, the characters from s1 and s2 should come in the exact order they appear in their respective strings.

For example, if s1 = "abc" and s2 = "def", then s3 = "adbcef" would be a valid interleaving. However, s3 = "abcdef" or s3 = "badcfe" would not be valid interleavings, because the relative ordering of the characters from s1 and s2 isn't respected in s3.

Intuition

The intuition for solving this problem lies in dynamic programming. We can imagine forming s3 character by character, making choices at each step of taking the next character from either s1 or s2. If at any point, the characters from s1 or s2 do not match the current character in s3, we cannot proceed further by that route.

The key insight for the solution is to construct a table (or array) that represents whether it is possible to form the prefix s3[0...k] from prefixes of s1 and s2. We initialize an array f of length n+1 (where n is the length of s2), which will help us track if s3 can be formed up to the j-th character of s2. We start by assuming that an empty s3 can be formed without any characters from either string (which is always true).

We then iterate over all characters in both s1 and s2, updating the array at each step. The condition f[j] &= s1[i - 1] == s3[k] checks if we can form the string by taking the next character from s1, while the condition f[j] |= f[j - 1] and s2[j - 1] == s3[k] checks if we can form the string by taking the next character from s2.

This way, we fill up the table iteratively, making sure at every step that we satisfy the condition of interleaving without violating the original order in the given strings. If, by the end of the iteration, we find that f[n] is True, it means that we can form s3 by interleaving s1 and s2. Otherwise, we cannot.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming, a method that solves problems by breaking them down into simpler subproblems and stores the results of those subproblems to avoid redundant computations.

Here's a step-by-step breakdown of the algorithm:

We begin by defining the lengths of s1 and s2 as m and n, respectively. Immediately, we check if the length of s3 is equal to the sum of the lengths of s1 and s2 (m + n). If not, s3 cannot be an interleaving of s1 and s2, and we return False.
We then create an array f of length n+1. f[j] will hold a boolean value indicating whether s3[0...i+j-1] is a valid interleaving of s1[0...i-1] and s2[0...j-1]. Here is a critical observation: f[0] is initialized to True because an empty string is considered an interleaving of two other empty strings by default.
We iterate through both strings s1 and s2 using two nested loops, one for index i ranging from 0 to m, and another for index j ranging from 0 to n. Each iteration represents an attempt to match the character in s3 at the current combined index k = i + j - 1.
For each pair (i, j), if i is not zero, we update f[j] to keep track of whether s3[k] can still match with the character in s1[i - 1]. This is indicated by the operation f[j] &= s1[i - 1] == s3[k].
Similarly, if j is not zero, we update f[j] to see if s3[k] can match with the character s2[j - 1], while also taking into account the value of f[j - 1], which indicates whether the interleaving was possible without considering the current character of s2. This happens with the operation f[j] |= f[j - 1] and s2[j - 1] == s3[k].
After both loops terminate, we return the value of f[n]. If f[n] is True, it means that s3 can be formed by interleaving s1 and s2. Otherwise, it means that it is not possible.

The above steps summarize the dynamic programming approach to solving the interleaving string problem. It's worth noting that the space complexity is optimized to O(n) since we are only using a single one-dimensional array to store the results.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a simple example to illustrate the solution approach. Consider the following strings:

s1 = "ax"
s2 = "by"
s3 = "abxy"

Here's how we'd walk through the algorithm:

First, we determine the lengths of s1 (length m = 2), and s2 (length n = 2). The length of s3 is 4, which is equal to m + n (2 + 2), so it's possible for s3 to be an interleaving of s1 and s2.
We create an array f with n+1 elements, which includes the initial condition (f[0] = True). Initially f = [True, False, False].
We begin iterating over the strings:

For i = 0 (considering an empty string for s1):
- For j = 0, f[0] remains True because an empty string can interleave with another empty string to form an empty string.
- For j = 1, since s2[0] ('b') matches s3[0] ('a'), f[1] remains False.
- For j = 2, since s2[1] ('y') does not match s3[1] ('b'), f[2] remains False. After checking, f = [True, False, False].
For i = 1 (considering the first character of s1):
- For j = 0, s1[0] ('a') matches s3[0] ('a'), so f[0] remains True.
- For j = 1, since s2[0] ('b') matches s3[1] ('b'), f[1] is updated to True.
- For j = 2, since s2[1] ('y') does not match s3[2] ('x'), f[2] remains False. After checking, f = [True, True, False].
For i = 2 (considering the second character of s1):
- For j = 0, s1[1] ('x') matches s3[2] ('x'), so f[0] remains True.
- For j = 1, since s2[0] ('b') does not match s3[3] ('y'), f[1] remains True.
- For j = 2, s2[1] ('y') matches s3[3] ('y'), and since f[1] is True, f[2] is updated to True. After checking, f = [True, True, True].

Once we have completed our iterations, the final f array is [True, True, True].
At the end, we examine the value of f[n], which in this case is True, indicating that s3 can indeed be formed by interleaving s1 and s2.

This completes the example walkthrough, showing that given the strings s1 = "ax", s2 = "by", and s3 = "abxy", s3 is a valid interleaving of s1 and s2 using the described dynamic programming approach.

Solution Implementation

1class Solution:
2    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
3        # Get the lengths of the input strings.
4        len_s1, len_s2 = len(s1), len(s2)
5
6        # If the combined length of s1 and s2 is not equal to the length of s3,
7        # it is impossible for s3 to be an interleaving of s1 and s2.
8        if len_s1 + len_s2 != len(s3):
9            return False
10
11        # Initialize a list to keep track of the possibility of interleaving up to each position.
12        # The +1 accounts for the empty substring. True implies that the interleaving is possible.
13        dp = [True] + [False] * len_s2
14
15        # Check if substrings of s1 can interleave with an empty s2 to form corresponding
16        # substrings of s3.
17        for i in range(len_s1 + 1):
18            for j in range(len_s2 + 1):
19                # k is the current index in s3 that we want to match.
20                k = i + j - 1
21                # If we are not at the first row, check if previous character in s1 matches with
22                # current character in s3. Use "&=" to modify the existing dp[j] value.
23                if i:
24                    dp[j] &= s1[i - 1] == s3[k]
25                # If we are not at the first column, check if the above cell or the left cell
26                # can lead to an interleaving. Use "|=" to incorporate this new possibility.
27                if j:
28                    dp[j] |= dp[j - 1] and s2[j - 1] == s3[k]
29
30        # The last element in the dp array contains the answer.
31        return dp[len_s2]
32
33# The function isInterleave returns True if s3 is an interleaving of s1 and s2, otherwise False.
34

1class Solution {
2    public boolean isInterleave(String s1, String s2, String s3) {
3
4        // Get the lengths of the strings
5        int m = s1.length(), n = s2.length();
6
7        // If the combined length of s1 and s2 does not equal the length of s3, return false
8        if (m + n != s3.length()) {
9            return false;
10        }
11
12        // Create a boolean array to keep track of the interleavings
13        boolean[] dp = new boolean[n + 1];
14        dp[0] = true;
15
16        // Iterate over each character of both s1 and s2
17        for (int i = 0; i <= m; ++i) {
18            for (int j = 0; j <= n; ++j) {
19
20                // Index k for matching characters in s3
21                int k = i + j - 1;
22
23                // If there are remaining characters in s1, check if they match s3's characters
24                if (i > 0) {
25                    dp[j] &= s1.charAt(i - 1) == s3.charAt(k);
26                }
27
28                // If there are remaining characters in s2, check if they match s3's characters
29                if (j > 0) {
30                    dp[j] |= (dp[j - 1] & (s2.charAt(j - 1) == s3.charAt(k)));
31                }
32            }
33        }
34
35        // Return whether it's possible to interleave s1 and s2 to get s3
36        return dp[n];
37    }
38}
39

1class Solution {
2public:
3    bool isInterleave(string s1, string s2, string s3) {
4        int length1 = s1.size(), length2 = s2.size();
5
6        // If the sum of lengths of s1 and s2 is not equal to length of s3,
7        // then s3 cannot be formed by interleaving s1 and s2
8        if (length1 + length2 != s3.size()) {
9            return false;
10        }
11
12        // dp array to hold the computed values; indicates if s3 up to a point
13        // is an interleaving of s1 and s2 up to certain points
14        bool dp[length2 + 1];
15
16        // Initialize the dp array to false
17        memset(dp, false, sizeof(dp));
18
19        // Base case: empty strings are considered interleaving
20        dp[0] = true;
21
22        // Iterate over characters in s1 and s2
23        for (int i = 0; i <= length1; ++i) {
24            for (int j = 0; j <= length2; ++j) {
25                // Calculate the corresponding index in s3
26                int indexS3 = i + j - 1;
27
28                // If we can take a character from s1 and it matches the corresponding character in s3,
29                // we maintain the value of dp[j] (continue to be true or false based on previous value)
30                if (i > 0) {
31                    dp[j] = dp[j] && (s1[i - 1] == s3[indexS3]);
32                }
33
34                // If we can take a character from s2 and it matches the corresponding character in s3,
35                // we update the value of dp[j] to be true if it's either true already or
36                // if previous element in dp array was true (indicating a valid interleave up to that point)
37                if (j > 0) {
38                    dp[j] = dp[j] || (s2[j - 1] == s3[indexS3] && dp[j - 1]);
39                }
40            }
41        }
42
43        // Return the last element in the dp array,
44        // which represents whether the whole s3 is an interleaving of s1 and s2
45        return dp[length2];
46    }
47};
48

1function isInterleave(s1: string, s2: string, s3: string): boolean {
2    const s1Length = s1.length;
3    const s2Length = s2.length;
4
5    // If the lengths of s1 and s2 together don't add up to the length of s3, they can't interleave to form s3.
6    if (s1Length + s2Length !== s3.length) {
7        return false;
8    }
9
10    // Initialize an array to hold the interim results of the dynamic programming solution.
11    // dp[i] will hold the truth value of whether s1 up to i characters can interleave with s2 up to j characters to form s3 up to i+j characters.
12    const dp: boolean[] = new Array(s2Length + 1).fill(false);
13
14    // Initialize the first value to true as an empty string is considered an interleave of two other empty strings.
15    dp[0] = true;
16
17    // Iterate over each character in s1 and s2 to build up the solution in dp.
18    for (let i = 0; i <= s1Length; ++i) {
19        for (let j = 0; j <= s2Length; ++j) {
20            // Calculate the corresponding index in s3.
21            const s3Index = i + j - 1;
22
23            // If we are not at the start of s1, determine if the current character of s1 is equal to the current character of s3
24            // and whether the result up to the previous character of s1 was true.
25            if (i > 0) {
26                dp[j] = dp[j] && s1[i - 1] === s3[s3Index];
27            }
28
29            // If we are not at the start of s2, determine if the current character of s2 is equal to the current character of s3
30            // and whether the result up to the previous character of s2 was true.
31            if (j > 0) {
32                dp[j] = dp[j] || (dp[j - 1] && s2[j - 1] === s3[s3Index]);
33            }
34        }
35    }
36
37    // The final result would be if s1 up to its full length can interleave with s2 up to its full length to form s3.
38    return dp[s2Length];
39}
40

Time and Space Complexity

The given Python code provides a solution to determine if a string s3 is formed by the interleaving of two other strings s1 and s2. Let's analyze both the time complexity and space complexity of the code.

Time Complexity

The outer loop in the code runs m + 1 times, where m is the length of s1. Within this loop, there's an inner loop that runs n + 1 times, where n is the length of s2. However, observe that for each outer iteration, the inner loop starts at 1 (since j ranges from 0 to n), so the combined iterations for the inner loop are actually m * (n + 1).

Each iteration of the inner loop consists of constant time checks and assignment operations, so its time complexity is O(1). Thus, the total time complexity for the double loop structure is O(m * (n + 1)). Simplifying, this is equivalent to O(m * n) since the addition of a constant 1 does not change the order of growth.

Therefore, the overall time complexity of the code is O(m * n).

Space Complexity

Space complexity considers the additional space used by the algorithm excluding the input sizes. In the code, a one-dimensional Boolean array f is initialized with n + 1 elements. The space usage of this array dominates the space complexity. There is no other data structure that grows with the input size. Thus, the space complexity is based on the size of f, which is O(n).

To summarize:

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

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don’t know