Introduction

In computer science, the concept of interleaving strings is a classic problem with applications in data processing, parsing, and concurrency control. The problem asks whether a string C is formed by interleaving two other strings A and B, preserving the character order within each source string. This article explains the problem, walks through the dynamic programming solution, and provides a complete worked example.

Problem Definition

A string C is an interleaving of strings A and B if C can be formed by merging A and B character by character, while maintaining the original left-to-right order of characters within both A and B.

For example, given:

• A = "abc"
• B = "def"

Then C = "adbcef" is an interleaving of A and B (take a from A, d from B, b from A, c from A, e from B, f from B).

But C = "abdfce" is not valid because c and e appear out of their original order relative to B.

Necessary Conditions

Before running the full algorithm, two quick checks can reject invalid inputs:

1. Length check: The length of C must equal the sum of the lengths of A and B:

$$|C| = |A| + |B|$$

1. Character check: The multiset of characters in C must equal the union of the multisets from A and B. If C contains a character not present in A or B, or the wrong count, the answer is immediately false.

Dynamic Programming Solution

Define a 2D boolean table $dp[i][j]$ that represents whether the first $i + j$ characters of C can be formed by interleaving the first $i$ characters of A with the first $j$ characters of B.

Initialization

$dp[0][0] = \text{true}$ because an empty C is trivially an interleaving of empty A and empty B.

For the first row ($i = 0$): $dp[0][j] = \text{true}$ if $B[0..j-1]$ matches $C[0..j-1]$.

For the first column ($j = 0$): $dp[i][0] = \text{true}$ if $A[0..i-1]$ matches $C[0..i-1]$.

Transition

For each cell $dp[i][j]$:

• If $A[i-1] = C[i+j-1]$ and $dp[i-1][j]$ is true, then $dp[i][j] = \text{true}$
• If $B[j-1] = C[i+j-1]$ and $dp[i][j-1]$ is true, then $dp[i][j] = \text{true}$
• Otherwise, $dp[i][j] = \text{false}$

Result

The answer is $dp[|A|][|B|]$.

Complexity

• Time: $O(n \times m)$ where $n = |A|$ and $m = |B|$
• Space: $O(n \times m)$ for the full table, or $O(\min(n, m))$ using a rolling array that keeps only the current and previous rows

Worked Example

Let A = "aab", B = "axy", and C = "aaxaby".

First, check the length: $|C| = 6 = 3 + 3 = |A| + |B|$. The check passes.

Build the DP table ($4 \times 4$):

Reading $dp[3][3] = \text{true}$, so "aaxaby" is an interleaving of "aab" and "axy".

Implementation

1def is_interleaving(a: str, b: str, c: str) -> bool:
2    if len(a) + len(b) != len(c):
3        return False
4
5    n, m = len(a), len(b)
6    dp = [[False] * (m + 1) for _ in range(n + 1)]
7    dp[0][0] = True
8
9    for i in range(n + 1):
10        for j in range(m + 1):
11            if i == 0 and j == 0:
12                continue
13            if i > 0 and a[i - 1] == c[i + j - 1] and dp[i - 1][j]:
14                dp[i][j] = True
15            if j > 0 and b[j - 1] == c[i + j - 1] and dp[i][j - 1]:
16                dp[i][j] = True
17
18    return dp[n][m]
19
20
21print(is_interleaving("aab", "axy", "aaxaby"))  # True
22print(is_interleaving("abc", "def", "abdfce"))   # False

Space-Optimized Version

Since each row of the DP table only depends on the current row and the row above, you can reduce space to $O(m)$ by using a single 1D array:

1def is_interleaving_optimized(a: str, b: str, c: str) -> bool:
2    if len(a) + len(b) != len(c):
3        return False
4
5    n, m = len(a), len(b)
6    dp = [False] * (m + 1)
7    dp[0] = True
8
9    for j in range(1, m + 1):
10        dp[j] = dp[j - 1] and b[j - 1] == c[j - 1]
11
12    for i in range(1, n + 1):
13        dp[0] = dp[0] and a[i - 1] == c[i - 1]
14        for j in range(1, m + 1):
15            dp[j] = (dp[j] and a[i - 1] == c[i + j - 1]) or \
16                    (dp[j - 1] and b[j - 1] == c[i + j - 1])
17
18    return dp[m]

Edge Cases

• All three strings are empty: returns true.
• One of A or B is empty: C must exactly equal the other string.
• A and B contain identical characters (e.g., A = "aa", B = "aa"): the DP correctly handles this since it tracks position within each source string independently.

Summary Table