Interweaving Strings

Tags

Interweaving Strings

Category

Recursion / Dynamic Programming

Difficulty

Hard

Problem Statement

Given three strings, determine whether the third string is an interleaving of the first two. A string is an interleaving of two other strings if it contains all characters from both strings in a way that maintains the left-to-right ordering of characters from each individual string, but the characters from the two strings can be interleaved in any fashion.

Intuition

At each position in the target string, the character must come from either the current position of string one or the current position of string two. This creates a decision tree that can be modeled as a 2D problem: given that we have consumed i characters from string one and j characters from string two, can we form the first i + j characters of the target? This overlapping subproblem structure makes it ideal for dynamic programming.

Approach

  1. First check if the length of the third string equals the sum of the lengths of the first two. If not, return false immediately.
  2. Create a 2D boolean DP table of size (len(one) + 1) x (len(two) + 1).
  3. dp[i][j] represents whether the first i + j characters of the target can be formed by interleaving the first i characters of string one and the first j characters of string two.
  4. Base case: dp[0][0] = true.
  5. Fill the first row: dp[0][j] is true if the first j characters of string two match the first j characters of the target.
  6. Fill the first column: dp[i][0] is true if the first i characters of string one match the first i characters of the target.
  7. For each cell dp[i][j], it is true if:
    • dp[i-1][j] is true and one[i-1] == target[i+j-1], OR
    • dp[i][j-1] is true and two[j-1] == target[i+j-1].
  8. Return dp[len(one)][len(two)].

Pseudocode

function interweavingStrings(one, two, three):
    if len(one) + len(two) != len(three):
        return false

    dp = 2D array of size (len(one) + 1) x (len(two) + 1), initialized to false
    dp[0][0] = true

    for j from 1 to len(two):
        dp[0][j] = dp[0][j-1] and two[j-1] == three[j-1]

    for i from 1 to len(one):
        dp[i][0] = dp[i-1][0] and one[i-1] == three[i-1]

    for i from 1 to len(one):
        for j from 1 to len(two):
            dp[i][j] = (dp[i-1][j] and one[i-1] == three[i+j-1]) or
                        (dp[i][j-1] and two[j-1] == three[i+j-1])

    return dp[len(one)][len(two)]

Time & Space Complexity

  • Time: O(n * m) where n and m are the lengths of the two input strings. Each cell is computed in O(1).
  • Space: O(n * m) for the DP table. Can be optimized to O(min(n, m)) using a rolling array since each row only depends on the previous row and the current row.

Key Insights

  • The length check is a critical early exit that avoids unnecessary computation.
  • The problem has optimal substructure: a valid interleaving up to position i + j depends on valid interleavings at smaller positions.
  • The 2D table can be visualized as a grid where you move right (consume from string two) or down (consume from string one), and you need a path from top-left to bottom-right.
  • A purely recursive solution without memoization has exponential time complexity due to overlapping subproblems.

Edge Cases

  • One or both input strings are empty — the target must equal the other non-empty string (or be empty if both are).
  • All three strings are empty — return true.
  • Target length does not equal sum of input lengths — immediately false.
  • Input strings have completely different character sets — many cells will be false, leading to early termination in practice.
  • Repeated characters in all strings — the DP correctly handles ambiguity about which string a character came from.

Linked mentions