Interleaving String (LeetCode 97)

The problem

You get three strings s1, s2 and s3. Return True if s3 can be formed by interleaving s1 and s2: taking all characters of both, keeping the order of each string, but mixing them in any way.

Input:  s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: True

One way: aa (from s1) + dbbc (s2) + bc (s1) + a (s2) + c (s1) gives aadbbcbcac.

How to think about it

Start with brute force. Walk through s3 and, at each character, try taking it from s1 or from s2 when both match. Every tie branches, so the worst case is O(2ᵐ⁺ⁿ).

Why greedy fails. When both strings offer the same next character, you don’t know which to take. Picking s1 first can dead-end later where picking s2 would have worked. That ambiguity is what DP resolves.

The key insight: the state is just how much of each string you’ve used. If you’ve used i characters of s1 and j of s2, you’ve built exactly s3[:i+j]. Let dp[i][j] mean “that is possible”. The last character s3[i+j-1] came either from s1[i-1] (so dp[i-1][j] must be true) or from s2[j-1] (so dp[i][j-1] must be true). So dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1]).

One row is enough. Each cell needs the cell above and the cell to the left, so a single array dp[j] works: before the update it holds “above”, and dp[j-1] is already “left”.

Which pattern is this? 2-D DP over two sequences, with a boolean cell. The tell is “can these two sequences combine into a third”, where ties make greedy unsafe.

Approach

1. If len(s1) + len(s2) != len(s3), return False.
2. Fill row 0 (no characters of s1): dp[0] = True, and dp[j] is true while s2[:j] equals s3[:j].
3. For each i from 1: update dp[0] (only s1 used so far), then each dp[j] with the recurrence.
4. Return dp[-1].

Solution

def is_interleave(s1, s2, s3):
    if len(s1) + len(s2) != len(s3): return False
    dp = [False]*(len(s2)+1); dp[0] = True        # dp[j] = can s1[:i], s2[:j] form s3[:i+j]
    for j in range(1, len(s2)+1): dp[j] = dp[j-1] and s2[j-1] == s3[j-1]   # row 0: only s2
    for i in range(1, len(s1)+1):
        dp[0] = dp[0] and s1[i-1] == s3[i-1]      # column 0: only s1
        for j in range(1, len(s2)+1):
            dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or (dp[j-1] and s2[j-1] == s3[i+j-1])   # from above (s1) or left (s2)
    return dp[-1]
# is_interleave("aabcc", "dbbca", "aadbbcbcac") -> True

Dry run

For the example, the dp row after each i (1 = True, 0 = False; columns j = 0..5):

The last cell of the last row is 1, so the answer is True. With s3 = "aadbbbaccc" it would be False.

Complexity

• Time: O(m · n). One update per pair (i, j).
• Space: O(n). One row of length len(s2) + 1.

Edge cases and pitfalls

• Length mismatch returns False immediately; skipping this check can index past the end of s3.
• All empty ("", "", "") returns True.
• Greedy “take from s1 when it matches” fails on inputs with shared characters, which is exactly the hard case.
• The s3 index is i + j - 1, not i or j; off-by-one here is the usual bug.

Related problems

• Longest Common Subsequence (LeetCode 1143): the same prefix-pair table, with numbers instead of booleans.
• Edit Distance (LeetCode 72): another two-string DP where each cell looks up, left and diagonally.
• Unique Paths (LeetCode 62): the same “above or left” shape; here a path through the grid is a way to interleave.