Strings Interleaving

Strings Interleaving

An interleaving of two strings m and n into p exists exactly when you can walk through p character by character while simultaneously advancing a pointer through m or a pointer through n (never both, never skipping) such that every character consumed matches the current character of p — this is a two-pointer feasibility problem with branching choices at each step, and branching choice + optimal substructure over a prefix pair is the signature of a 2D dynamic program: state (i, j) = "can the first i chars of m and first j chars of n interleave to form the first i+j chars of p?"

Recognize the pattern

• Two source sequences must be merged, preserving each one's internal order, into a target sequence — relative order matters, but the two sources can be freely shuffled against each other.
• The target length always equals the sum of the two source lengths (a hard prerequisite check before doing any real work).
• You are asked "can this be formed" (feasibility), not "count the ways" or "find the shuffle" — though the same table answers all three with minor changes.
• Naive recursive attempts re-derive the same (i, j) subproblem from multiple paths — a strong signal to memoize.

Brute force → optimal

Brute force: at each position of p, try consuming from m if it matches, try consuming from n if it matches, and recurse on both branches, backtracking on failure. With |m|=a and |n|=b, the number of ways to fully interleave the two strings (ignoring character content) is C(a+b, a) — that is a count of possible merges, not a running time. The recursion's actual work is bounded by the size of its call tree: every internal node can spawn up to two children (try-from-m, try-from-n), and a path can be as long as a+b steps before failing or succeeding, so the tree has at most O(2^(a+b)) nodes in the worst case. These are two different quantities — C(a+b,a) counts only the branches that survive as full valid merges; O(2^(a+b)) bounds the total number of nodes explored, including every branch that dies early on a character mismatch. The brute force is exponential time, O(a+b) recursion-stack space.

Optimal: notice the recursion only ever depends on how many characters of m and how many of n have been consumed so far — never on which path got you there. That collapses the exponential tree onto an (a+1)×(b+1) grid of distinct states, each computed once: bottom-up DP.

Complexity, derived

State space: (a+1) × (b+1) cells for dp[i][j]. Each cell does O(1) work — two constant-time character comparisons and two constant-time table lookups (from dp[i-1][j] and dp[i][j-1]). Total operations = cells × work/cell = O(a·b) time. Space is the table itself, O(a·b), reducible to O(b) (or O(min(a,b))) by keeping only the previous row, since row i only reads row i-1 and the current row's left neighbor.

Worked example

m = "abd" (a=3), n = "cef" (b=3), p = "abcdef" (length 6, matches a+b — passes the pre-check). Recurrence: dp[i][j] = (dp[i-1][j] and m[i-1]==p[i+j-1]) or (dp[i][j-1] and n[j-1]==p[i+j-1]), with dp[0][0]=true. Full table (T/F), rows = prefixes of m, columns = prefixes of n:

Tracing the true cells that lead to the answer: dp[1][0]=T since m[0]='a'==p[0]. dp[2][0]=T since m[1]='b'==p[1]. dp[1][1]=F: fromM needs dp[0][1] (F); fromN needs n[0]='c'==p[1]='b' (no). dp[2][1]: p[2]='c' matches n[0]='c' with dp[2][0]=T → T. dp[2][2]=F: fromM needs dp[1][2] (F); fromN needs n[1]='e'==p[3]='d' (no). dp[3][1]: p[3]='d' matches m[2]='d' with dp[2][1]=T → T. dp[3][2]: p[4]='e' matches n[1]='e' with dp[3][1]=T → T. dp[3][3]: p[5]='f' matches n[2]='f' with dp[3][2]=T → T. Final answer dp[3][3] = true, matching the take-alternately-then-finish-n interleaving a,b,c,d,e,f.

Java (bottom-up, O(a·b) time, O(b) space)

public boolean isInterleave(String m, String n, String p) {
    int a = m.length(), b = n.length();
    if (a + b != p.length()) return false;
    boolean[] dp = new boolean[b + 1];
    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {
            if (i == 0 && j == 0) {
                dp[j] = true;
            } else if (i == 0) {
                dp[j] = dp[j - 1] && n.charAt(j - 1) == p.charAt(j - 1);
            } else if (j == 0) {
                dp[j] = dp[j] && m.charAt(i - 1) == p.charAt(i - 1);
            } else {
                boolean fromM = dp[j] && m.charAt(i - 1) == p.charAt(i + j - 1);
                boolean fromN = dp[j - 1] && n.charAt(j - 1) == p.charAt(i + j - 1);
                dp[j] = fromM || fromN;
            }
        }
    }
    return dp[b];
}

Note the row-reuse subtlety: when j==0, dp[j] on the right side still holds the value from row i-1 (no earlier write in this row has touched it yet), so it correctly represents dp[i-1][0].

Pitfalls

• Skipping the length pre-check (a + b == p.length()) and letting the DP run anyway — wastes time and can index out of bounds.
• In the 1D-rolled version, computing dp[j] before reading the stale "previous row" value at the same index — order of the i==0/j==0/general branches matters.
• Off-by-one on p.charAt(i + j - 1): the character being matched is the (i+j)-th of p, 1-indexed, hence -1.
• Assuming greedy "match m first, else n" works — it doesn't; only full DP (or backtracking) correctly explores both choices, since a locally-valid greedy match can dead-end later.
• Confusing C(a+b,a) (count of valid full merges) with the brute-force recursion's O(2^(a+b)) node bound (count of all explored branches, valid or not) — they answer different questions and one is not derived from the other.

When to use / when NOT — trade-offs

Use this DP when you need a definitive yes/no over all possible merges and inputs are small-to-moderate (a,b ≤ ~1000 fits comfortably in O(a·b)). Alternative — recursion + memoization (top-down): same O(a·b) time/space, easier to write correctly from the brute-force recursion, but pays recursion-stack overhead and risks stack overflow on long strings; prefer bottom-up for production code and top-down for quick correctness-first prototyping. Alternative — plain backtracking (no memo): only viable when strings are tiny or mostly forced (few branch points), since it's exponential in the worst case; do not use it as a general solution.

Takeaways

• Interleaving is a 2D prefix-pair DP: state = how much of each source has been consumed, transition = which source contributed the last character of p.
• Always check |m|+|n| == |p| first — a free O(1) rejection.
• The DP collapses an exponential number of merge-orders onto O(a·b) distinct states because the recursion never needs to know the specific path, only the counts consumed.
• Space optimizes from O(a·b) to O(min(a,b)) via row-rolling, same as most 2D-grid DPs (edit distance, LCS).

Recall: Why does dp[i][j] depend only on dp[i-1][j] and dp[i][j-1], and never on any state where fewer than i+j-1 total characters have been consumed?

Pattern: Interleaving Strings — related to Edit Distance and Longest Common Subsequence via the shared 2D prefix-grid DP structure (Educative Grokking the Coding Interview; CLRS DP chapter).