The problem
Given strings A, B and C, decide whether C can be made by interleaving A and B: weaving them together while keeping each one’s letters in their original order.
Input: A = "aabcc", B = "dbbca", C = "aadbbcbcac" Output: true
Picture it
Picture braiding two ribbons into one. The table’s cell (i, j) asks: can the first i letters of A and the first j letters of B make the first i + j letters of the braid? We can get there from above (the last letter came from A and it matches) or from the left (it came from B and matches).
How to recognise it
- Two sequences must be merged into a third while each keeps its own internal order.
- At every step of building the result, there are two choices: take the next letter from A or from B.
- A greedy pick can be wrong, because both A and B may offer the same next letter.
- The state is how much of A and how much of B has been used, which also fixes how much of C has been explained.
- Lengths up to 100 and 200 rule out trying every way to weave the strings.
Start with brute force
C has m + n letters, and an interleaving decides which m of those positions come from A. Try every choice of those positions and check whether the letters match.
from itertools import combinations
def interleave_brute(a, b, c):
if len(a) + len(b) != len(c):
return False
n = len(c)
for pos in combinations(range(n), len(a)): # positions taken from a
from_a = set(pos)
ai, bi = iter(a), iter(b)
if all((next(ai) if k in from_a else next(bi)) == c[k] for k in range(n)):
return True
return False
There are C(m + n, m) choices, each checked in O(m + n). With m = n = 100 that is about 9 × 10^58 choices. Space is O(m + n).
From brute force to the idea
- Find the waste. Many different weavings reach the same point: "I have used i letters of A and j of B". The rest of the problem depends only on (i, j).
- C is already pinned down. If i letters of A and j of B are used, exactly i + j letters of C have been explained. So no third index is needed.
- Define the table.
ok[i][j]is True if the first i letters of A and the first j letters of B can weave into the first i + j letters of C. - Two ways in. The last letter of that prefix of C,
c[i+j-1](calledkin the code), came either from A or from B. If it came from A, thena[i-1]must equal it andok[i-1][j]must be True. If from B, thenb[j-1]must equal it andok[i][j-1]must be True. Either way makes the cell True. - Start and answer.
ok[0][0]is True (nothing used, nothing to explain), andok[m][n]is the answer. A first check thatlen(a) + len(b) == len(c)rejects hopeless inputs at once.
This is the key idea: the pair (i, j) is enough to know where you are in C, so a table of m × n booleans replaces the exponential search.
The key idea
dp[i][j] = (dp[i−1][j] and A[i−1] == C[i+j−1]) or (dp[i][j−1] and B[j−1] == C[i+j−1]). O(m × n).
Python solution
def is_interleave(a, b, c):
if len(a) + len(b) != len(c): return False
ok = [[False] * (len(b) + 1) for _ in range(len(a) + 1)]
ok[0][0] = True
for i in range(len(a) + 1):
for j in range(len(b) + 1):
k = i + j - 1 # next letter of c to explain
if i and a[i - 1] == c[k] and ok[i - 1][j]: ok[i][j] = True
if j and b[j - 1] == c[k] and ok[i][j - 1]: ok[i][j] = True
return ok[len(a)][len(b)]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(C(m + n, m) · (m + n)): every choice of positions is checked | O(m + n): one set of positions |
| DP table (shown code) | O(m · n): one constant-time step per cell | O(m · n): the whole table; one row would be enough for O(n) |
Edge cases
- Length mismatch: returns False immediately. Without this check the code breaks (see the quiz).
- All three empty: returns True, since
ok[0][0]is True. - One string empty:
("a", "", "a")is True, and("ab", "", "ba")is False, because C must equal the other string. - Greedy trap:
"aa","ab","abaa"is True (takeabfrom B first, thenaafrom A). A greedy rule "take from A if it matches" grabs A's first letter, gets stuck and answers False, while the table answers True. - At cell (0, 0) the code computes
k = -1, but theif iandif jtests stopc[k]from being read.
Common mistakes
- Matching greedily (take from A whenever it matches), which fails when both strings offer the same letter.
- Skipping the length check, so a longer C with an unused tail can be accepted.
- Using
c[i]orc[j]as the letter to explain instead ofc[i + j - 1].
Instead of true or false, return how many different ways C can be woven from A and B (a way is a choice of which positions of C come from A). For "a", "a", "aa" the answer is 2. Describe your approach, then write it if you like.
Compare with our answer
Same table, but each cell stores a count and the two ways in are added instead of combined with "or". Different position choices stay different even when the letters are equal.
def count_interleavings(a, b, c):
if len(a) + len(b) != len(c):
return 0
ways = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
ways[0][0] = 1
for i in range(len(a) + 1):
for j in range(len(b) + 1):
k = i + j - 1
if i and a[i - 1] == c[k]:
ways[i][j] += ways[i - 1][j]
if j and b[j - 1] == c[k]:
ways[i][j] += ways[i][j - 1]
return ways[len(a)][len(b)]
count_interleavings("aa", "aa", "aaaa") is 6, ("ab", "ab", "abab") is 2, and ("", "", "") is 1. Time and space O(m · n).
A strong answer mentions: replacing True/False with counts, adding the two sources, and the count for empty strings being 1.
1. You must decide whether a string C is a merge of A and B where each keeps its order, and A and B can share letters. Which approach fits best?
The state (i, j) fixes how much of C is explained, and both sources may match, so both must be tried. A greedy scan can pick the wrong one, and counting letters ignores order.
2. Why is the shown code O(m · n) rather than exponential?
The rest of the problem depends only on (i, j), so all weavings reaching that pair are merged into one cell. The loops always fill the whole table; there is no early stop.
3. The first line of the function, if len(a) + len(b) != len(c): return False, is deleted. What does the code return for a = "ab", b = "cd", c = "abcdx"?
The cell (2, 2) reads only c[0] to c[3], so the extra x is never examined and the code wrongly answers True. A c that is too short, by contrast, raises IndexError.
Score 60% or more and the lesson is marked complete.