Interleaving String

Updated on 02 June, 2025
Interleaving String header image

Problem Statement

The task is to determine whether a string s3 can be formed by interleaving two other strings s1 and s2. The concept of interleaving here involves splitting s1 and s2 into several substrings and reassembling these pieces intercalatedly to produce s3. Specifically, s1 and s2 are divided into substrings such that their concatenation in an alternate fashion results in s3. The interleaving pattern should either start with a substring from s1 followed by one from s2 or vice versa, continuing this pattern throughout. It's also required that the absolute difference in the number of pieces into which s1 and s2 are divided does not exceed one.

Examples

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.

Approach and Intuition

The key to solving the problem of checking if s3 is an interleaving of s1 and s2 lies in exploring all possible interleaved combinations that s1 and s2 can produce and seeing if any of these match s3. Below follows a logical breakdown based on insights from the examples provided:

  1. Dynamic Programming Table Initialization:

    • Consider a 2D array dp where dp[i][j] indicates whether the first i characters of s1 and the first j characters of s2 can interleave to form the first i+j characters of s3.
    • Initialize dp[0][0] = true (empty strings interleaving to form an empty string).
  2. Fill the DP Table:

    • For each character position in s1 and s2, determine if that character can extend an existing interleaving from s3.
    • Specifically, check if dp[i][j] = true under two conditions:
      • If the last character added from s1 matches the current character in s3 and dp[i-1][j] was true.
      • If the last character added from s2 matches the current character in s3 and dp[i][j-1] was true.
  3. Edge Cases:

    • When one of s1 or s2 is empty, s3 should be entirely made of the other non-empty string.
    • If the combined length of s1 and s2 does not match the length of s3, it’s impossible for s3 to be an interleaving of s1 and s2.

Examples from user input demonstrate this logic:

  • Example 1:

    • s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
    • Through careful selection and interleaving of substrings from s1 and s2, s3 is achievable.
  • Example 2:

    • A mismatch in desired subsequence characters points to s3 not being a possible interleaving.
  • Example 3:

    • All strings are empty. Trivially, an empty string is an interleaving of two empty strings.

Through this approach, one can systematically determine whether s3 is a result of interleaving s1 and s2 by filling up a dynamic programming table and consulting its last cell to check for feasibility. This method ensures that all potential segmentations and interleavings are considered.

Solutions

  • C++
  • Java
  • C
  • JavaScript
  • Python
cpp
class Solution {
public:
    bool checkInterleavings(string str1, string str2, string str3) {
        int len1 = str1.length(), len2 = str2.length(), len3 = str3.length();
        if (len3 != len1 + len2) {
            return false;
        }
        vector<bool> interleaved(len2 + 1, false);
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                if (i == 0 && j == 0) {
                    interleaved[j] = true;
                } else if (i == 0) {
                    interleaved[j] = interleaved[j - 1] && str2[j - 1] == str3[i + j - 1];
                } else if (j == 0) {
                    interleaved[j] = interleaved[j] && str1[i - 1] == str3[i + j - 1];
                } else {
                    interleaved[j] = (interleaved[j] && str1[i - 1] == str3[i + j - 1]) ||
                                     (interleaved[j - 1] && str2[j - 1] == str3[i + j - 1]);
                }
            }
        }
        return interleaved[len2];
    }
};

The provided C++ solution addresses the problem of determining if a string str3 is an interleaving of two other strings str1 and str2. The code relies on dynamic programming to efficiently solve the problem, represented by the function checkInterleavings.

  • Start by declaring and initializing three integer variables, len1, len2, and len3, representing the lengths of str1, str2, and str3 respectively. Check if the length of str3 is equal to the sum of the lengths of str1 and str2. If not, return false since str3 cannot possibly be an interleaving.
  • Use a boolean vector interleaved to keep track of whether certain segments of str2 can form an interleaving up to each index when combined with segments of str1.
  • In a nested loop, iterate over all possible splits between str1 and str2:
    • If both indices (i and j) representing positions in str1 and str2 are zero, initialize interleaved[j] as true.
    • If only i is zero, check if the segment of str2 up to index j alone can match with str3 up to index i + j, updating interleaved[j] accordingly.
    • If only j is zero, perform a similar check for str1 and update interleaved[j].
    • Otherwise, update interleaved[j] to reflect whether its previous value or the value of interleaved[j-1] (indicating different possible interleavings from str1 and str2) matches with str3.
  • Finally, return the last value in the interleaved vector, which indicates whether the full strings can be interleaved to form str3.

This method provides an efficient solution to the problem by using a single-dimensional DP table instead of a two-dimensional one, optimizing the space complexity. The overall approach ensures checks at each position if the characters of str1 and str2 can compose str3 in a recursive manner while storing the states to avoid redundant calculations.

java
public class Solution {
    public boolean checkInterleaved(String str1, String str2, String mergedStr) {
        if (mergedStr.length() != str1.length() + str2.length()) {
            return false;
        }
        boolean[] flags = new boolean[str2.length() + 1];
        for (int i = 0; i <= str1.length(); i++) {
            for (int j = 0; j <= str2.length(); j++) {
                if (i == 0 && j == 0) {
                    flags[j] = true;
                } else if (i == 0) {
                    flags[j] = flags[j - 1] &&
                    str2.charAt(j - 1) == mergedStr.charAt(i + j - 1);
                } else if (j == 0) {
                    flags[j] = flags[j] && str1.charAt(i - 1) == mergedStr.charAt(i + j - 1);
                } else {
                    flags[j] = (flags[j] &&
                        str1.charAt(i - 1) == mergedStr.charAt(i + j - 1)) ||
                    (flags[j - 1] && str2.charAt(j - 1) == mergedStr.charAt(i + j - 1));
                }
            }
        }
        return flags[str2.length()];
    }
}

The provided Java solution tackles the problem of determining whether a string mergedStr can be formed by interleaving two other strings str1 and str2. Here’s how the solution efficiently approaches the problem:

  • First, ensure that the length of mergedStr is exactly equal to the sum of the lengths of str1 and str2. If not, mergedStr cannot be an interleaved string, and the function returns false immediately.

  • Utilize a boolean array flags with a size of str2.length() + 1 to keep track of whether a substring of mergedStr can be formed by interleaving substrings of str1 and str2 up to certain lengths.

  • Iterate over every possible prefix length of str1 and str2. For each combination of substrings lengths from str1 and str2 (denoted as i and j), update the flags array based on the following conditions:

    • If either i or j is 0, initialize flags[j] based on whether the previous characters in flags and corresponding characters in str2, or str1 match the current character in mergedStr.
    • For other values of i and j, set flags[j] to true if:
      • The current character in mergedStr matches the last character of the current str1 prefix and the remainder formed by interleaving is valid.
      • The current character in mergedStr matches the last character of the current str2 prefix and the remainder formed by interleaving is valid.
  • The value at flags[str2.length()] will ultimately indicate whether the entire mergedStr can be formed by interleaving str1 and str2.

The core idea is to dynamically build up the solution using previously computed results, greatly reducing the complexity and improving efficiency compared to a naive approach. This smart design ensures the solution is both optimal and clean, focusing solely on whether interleaving is possible without constructing the actual interleaved string.

c
bool checkInterleave(char* str1, char* str2, char* str3) {
    int length1 = strlen(str1), length2 = strlen(str2), length3 = strlen(str3);
    if (length3 != length1 + length2) {
        return false;
    }
    bool interleave[length2 + 1];
    memset(interleave, false, sizeof(interleave));
    for (int idx1 = 0; idx1 <= length1; idx1++) {
        for (int idx2 = 0; idx2 <= length2; idx2++) {
            if (idx1 == 0 && idx2 == 0) {
                interleave[idx2] = true;
            } else if (idx1 == 0) {
                interleave[idx2] = interleave[idx2 - 1] && str2[idx2 - 1] == str3[idx1 + idx2 - 1];
            } else if (idx2 == 0) {
                interleave[idx2] = interleave[idx2] && str1[idx1 - 1] == str3[idx1 + idx2 - 1];
            } else {
                interleave[idx2] = (interleave[idx2] && str1[idx1 - 1] == str3[idx1 + idx2 - 1]) ||
                                   (interleave[idx2 - 1] && str2[idx2 - 1] == str3[idx1 + idx2 - 1]);
            }
        }
    }
    return interleave[length2];
}

The C function checkInterleave checks whether a string str3 is an interleaving of two other strings, str1 and str2. An interleaving string contains all characters from both strings and maintains the relative order of characters from each string.

  • The function begins by calculating the lengths of str1, str2, and str3 using strlen.
  • If the length of str3 is not equal to the sum of the lengths of str1 and str2, it directly returns false, indicating that str3 cannot be an interleaving of str1 and str2.
  • An array interleave of type bool with a size of length2 + 1 is initialized to store intermediate validation results.
  • The memset function initializes all elements in the interleave array to false.

The core part of the function is a nested loop iterating over each character of str1 and str2. The loops perform the following checks:

  • If both indexes idx1 and idx2 are zero, then the starting point is set to true as there is no character to check yet.
  • For the edge cases where idx1 is zero or idx2 is zero, the function verifies if continuing from previous characters will still satisfy interleaving up to the current index by comparing parts from str2 or str1 with str3 respectively.
  • For general cases, the function checks two conditions:
    • If continuing from the last character of str1 is possible.
    • Or, if continuing from the last character of str2 is possible.

The function ultimately returns the value of interleave[length2], which represents whether str3 can be constructed by interleaving str1 and str2 entirely by index length2 of str2.

js
var interleavedStrings = function (str1, str2, combined) {
    if (combined.length !== str1.length + str2.length) {
        return false;
    }
    let check = new Array(str2.length + 1).fill(false);
    for (let x = 0; x <= str1.length; x++) {
        for (let y = 0; y <= str2.length; y++) {
            if (x === 0 && y === 0) {
                check[y] = true;
            } else if (x === 0) {
                check[y] = check[y - 1] && str2[y - 1] === combined[x + y - 1];
            } else if (y === 0) {
                check[y] = check[y] && str1[x - 1] === combined[x + y - 1];
            } else {
                check[y] = 
                    (check[y] && str1[x - 1] === combined[x + y - 1]) ||
                    (check[y - 1] && str2[y - 1] === combined[x + y - 1]);
            }
        }
    }
    return check[str2.length];
};

The provided JavaScript function interleavedStrings determines if the string combined can be formed by interleaving the characters of two other strings str1 and str2. This function uses dynamic programming as its underlying solution approach.

  • The function starts by checking if the combined string's length is equal to the sum of the lengths of str1 and str2. If not, it immediately returns false.
  • Initialize a boolean array check with a length of str2.length + 1 and set all values to false. This array helps keep track of previously computed results to avoid redundant calculations.
  • Utilize nested loops where x iterates through str1 and y through str2. The function updates the check array based on conditions:
    • When both x and y are zero, set check[y] to true.
    • If only x is zero, set check[y] based on the comparison between the last character of the section of str2 considered so far and the corresponding character in combined.
    • If only y is zero, adjust check[y] based on the comparison between the last character of the section of str1 considered so far and the corresponding character in combined.
    • For other values of x and y, set check[y] to true if either of the following conditions are met:
      • check[y] is true, and the character from str1 matches the corresponding character in combined.
      • The previous value check[y-1] is true, and the character from str2 matches the corresponding character in combined.
  • Finally, return the value of check[str2.length] to determine if combined can indeed be formed by interleaving str1 and str2.

The dynamic programming approach helps optimize the interleaving check by breaking it down into smaller subproblems, each defining a possible interleaving at different stages with entries x and y. This leads to a more efficient solution compared to naive recursive methods.

python
class Solution:
    def checkInterleaved(self, str1: str, str2: str, str3: str) -> bool:
        if len(str3) != len(str1) + len(str2):
            return False
        dp_table = [False] * (len(str2) + 1)
        for idx1 in range(len(str1) + 1):
            for idx2 in range(len(str2) + 1):
                if idx1 == 0 and idx2 == 0:
                    dp_table[idx2] = True
                elif idx1 == 0:
                    dp_table[idx2] = dp_table[idx2 - 1] and str2[idx2 - 1] == str3[idx1 + idx2 - 1]
                elif idx2 == 0:
                    dp_table[idx2] = dp_table[idx2] and str1[idx1 - 1] == str3[idx1 + idx2 - 1]
                else:
                    dp_table[idx2] = (dp_table[idx2] and str1[idx1 - 1] == str3[idx1 + idx2 - 1]) or (
                        dp_table[idx2 - 1] and str2[idx2 - 1] == str3[idx1 + idx2 - 1]
                    )
        return dp_table[len(str2)]

This Python solution involves a function checkInterleaved that determines if a string str3 is an interleaving of two other strings, str1 and str2. The function uses dynamic programming to solve the problem efficiently:

  • Initially, it checks if the combined length of str1 and str2 matches the length of str3. If not, it returns False immediately.
  • A one-dimensional list dp_table is utilized to keep track of the interleaving status. This list is initialized with False values, representing that no interleaving has been determined yet.
  • The list size corresponds to the length of str2 plus one (for base cases).

The solution iteratively fills the dp_table using conditions based on character matches between str3 and the respective characters of str1 and str2:

  • It sets the initial condition where if no characters are taken from either str1 or str2, the interleaving condition is naturally True (dp_table[0] is True).
  • For characters from str2, it updates the state based on previous values in the dp_table.
  • For characters from str1, it uses either the current or previous values from the dp_table to update the interleaving state.
  • Each state dp_table[idx2] is updated based on whether str1[idx1-1] or str2[idx2-1] matches with str3[idx1+idx2-1], indicating if a valid interleaving can include the current character.

Finally, the function returns the value at dp_table[len(str2)], which indicates if the entire str3 can be formed by interleaving all characters of str1 and str2. This approach provides a clear and efficient solution to the interleaving string problem using dynamic programming principles.

Comments

No comments yet.