Interleaving String LeetCode 97 Guide

LeetCode 97 — Interleaving String — gives you three strings s1, s2, and s3. Determine if s3 is formed by an interleaving of s1 and s2. An interleaving of two strings preserves the left-to-right order of characters from each string but allows them to be interwoven.

For example, s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" is a valid interleaving. You can trace through s3 picking characters alternately from s1 and s2 while maintaining their original order. But s3 = "aadbbbaccc" is not a valid interleaving.

The problem has a clean 2D DP formulation: dp[i][j] represents 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. The answer is dp[m][n] where m and n are the lengths of s1 and s2.

Define dp[i][j] = true if s1[0..i-1] and s2[0..j-1] can interleave to form s3[0..i+j-1]. Base case: dp[0][0] = true (empty strings interleave to empty string). First row: dp[0][j] = dp[0][j-1] AND s2[j-1] == s3[j-1]. First column: dp[i][0] = dp[i-1][0] AND s1[i-1] == s3[i-1].

For the general case, the last character of s3[i+j-1] must come from either s1[i-1] or s2[j-1]. If s1[i-1] == s3[i+j-1], then dp[i][j] can be true if dp[i-1][j] is true (the rest was already interleaved). Similarly, if s2[j-1] == s3[i+j-1], dp[i][j] can be true if dp[i][j-1] is true.

The full transition is: 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]). This captures both possibilities: the last character came from s1 or from s2.

Consider s1 = "ab", s2 = "cd", s3 = "acbd". m=2, n=2, len check: 2+2=4 OK. Build 3x3 DP table. dp[0][0]=T. Row 0: dp[0][1]: s2[0]=c vs s3[0]=a → F. dp[0][2]: F (propagates). Col 0: dp[1][0]: s1[0]=a vs s3[0]=a → T. dp[2][0]: s1[1]=b vs s3[1]=c → F.

dp[1][1]: from dp[0][1](F) with s1[0]=a==s3[1]=c? No. From dp[1][0](T) with s2[0]=c==s3[1]=c? Yes! dp[1][1]=T. dp[1][2]: from dp[0][2](F) or from dp[1][1](T) with s2[1]=d==s3[2]=b? No. dp[1][2]=F.

dp[2][1]: from dp[1][1](T) with s1[1]=b==s3[2]=b? Yes! dp[2][1]=T. dp[2][2]: from dp[1][2](F) or from dp[2][1](T) with s2[1]=d==s3[3]=d? Yes! dp[2][2]=T. Return true. The interleaving is a-c-b-d.

Each row of the DP table only depends on the current row (dp[i][j-1]) and the previous row (dp[i-1][j]). We can compress to a single 1D array of size n+1. Process row by row: dp[j] represents dp[i][j] for the current i.

For each i from 1 to m, update dp[j] for j from 0 to n. dp[0] = dp[0] AND s1[i-1] == s3[i-1] (first column). For j from 1 to n: dp[j] = (dp[j] AND s1[i-1] == s3[i+j-1]) OR (dp[j-1] AND s2[j-1] == s3[i+j-1]). Here dp[j] on the right side is the value from the previous row.

This reduces space from O(m*n) to O(n). The time remains O(m*n). This optimization is standard for 2D DP problems where each cell depends only on its top and left neighbors.

In Python 2D: dp = [[False]*(n+1) for _ in range(m+1)]. dp[0][0] = True. Fill first row and column, then the rest with the transition formula. Return dp[m][n]. About 15 lines of clean code.

In Python 1D: dp = [False]*(n+1). dp[0] = True. Fill dp[j] for j=1..n for the first row. Then for each i=1..m, update dp[0] and dp[1..n] using the compressed formula. Return dp[n].

In Java, the 2D version uses boolean[][] and the 1D version uses boolean[]. The logic is identical. Java's boolean default is false, so only dp[0][0] = true needs explicit initialization.

Time complexity is O(m * n) where m = len(s1) and n = len(s2). We fill each cell of the DP table exactly once with O(1) work per cell. With constraints m, n <= 100, this is at most 10,000 operations.

Space complexity is O(m * n) for the 2D version or O(n) for the 1D optimized version. Both are efficient for the given constraints.

A BFS/DFS approach also works: treat (i, j) as a state meaning we have consumed i chars from s1 and j chars from s2. Explore neighbors (i+1, j) and (i, j+1) if the characters match. With memoization, this is equivalent to the DP but less clean.

Edit Distance (LeetCode 72) uses the same 2D DP structure on two strings with three transitions (insert, delete, replace). Interleaving String has two transitions (take from s1 or s2). Both problems fill a table where dp[i][j] depends on dp[i-1][j] and dp[i][j-1].

Distinct Subsequences (LeetCode 115) counts subsequences of s matching t, using dp[i][j] = dp[i-1][j-1] + dp[i-1][j]. The three problems — Edit Distance, Distinct Subsequences, and Interleaving String — form the canonical 2D string DP set.

Longest Common Subsequence (LeetCode 1143) is another 2D string DP that finds the length of the longest shared subsequence. It serves as a simpler warm-up before tackling the more complex transition rules in Interleaving String.