Interleaving String

1. Problem & Core Objective

Return true if s3 is formed by interleaving s1 and s2 — that is, by merging them while preserving each one's internal order.

s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"   →  true
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"   →  false
s1 = "", s2 = "", s3 = ""                        →  true

Constraints: 0 <= s1.length, s2.length <= 100 · 0 <= s3.length <= 200 · lowercase

What's actually being tested: that greedy fails — when both strings offer the same next character, you can't know which to consume — and that the state is (i, j) with k = i + j derived, not tracked separately. Recognising that third index is redundant is what keeps it 2-D.

2. First-Principles Thought Process

Why greedy fails

At each step, take the next character of s3. If only one of s1, s2 offers it, the choice is forced. But if both do, greedy has no basis for choosing — and picking wrong can dead-end later.

s1 = "aa", s2 = "ab", s3 = "aaab"

The first a could come from either. Committing to one may strand the other.

So both branches must be explored, which is a search — and the overlapping subproblems make it a DP.

The state, and the index that isn't needed

dp[i][j] = "can s3's first i + j characters be formed from s1's first i and s2's first j?"

k = i + j is derived, not stored. If i characters come from s1 and j from s2, exactly i + j of s3 have been consumed — there's no freedom.

Tracking k separately would make it a 3-D table with 100 × 100 × 200 cells, most of them unreachable. Noticing the dependency keeps it 101 × 101.

The recurrence

dp[i][j] = (dp[i-1][j] AND s1[i-1] == s3[i+j-1])      take from s1
        OR (dp[i][j-1] AND s2[j-1] == s3[i+j-1])      take from s2

Existence question, so the combiner is ||.

The length check comes first

If s1.length + s2.length != s3.length, no interleaving exists. An O(1) rejection — and without it the indexing would run off the end.

Base cases

dp[0][0] = true — empty from empty.

Row 0 and column 0 are prefix matches: dp[0][j] is true only if s2's first j characters exactly equal s3's first j.

3. Solution Paths

Approach 1 — Recursion over both choices

public boolean isInterleave(String s1, String s2, String s3) {
    if (s1.length() + s2.length() != s3.length()) return false;
    return check(s1, s2, s3, 0, 0);
}

private boolean check(String s1, String s2, String s3, int i, int j) {
    if (i == s1.length() && j == s2.length()) return true;
    int k = i + j;                                   // derived, not passed

    if (i < s1.length() && s1.charAt(i) == s3.charAt(k) && check(s1, s2, s3, i + 1, j))
        return true;
    if (j < s2.length() && s2.charAt(j) == s3.charAt(k) && check(s1, s2, s3, i, j + 1))
        return true;
    return false;
}

• Time O(2^(m+n)) · Space O(m + n) stack

Counter-questions on this approach

⭐ "Why can't you just take whichever string matches?"

Because both may match. With s1 = "aa", s2 = "ab", s3 = "aaab", the first character of s3 is a and both strings offer it. Committing to one can dead-end.

Greedy needs a rule that's always correct, and there isn't one here — so both branches must be explored.

⭐ "Why is k computed rather than passed?"

Because it's fully determined: consuming i from s1 and j from s2 means exactly i + j of s3 are used. There's no scenario where the same (i, j) corresponds to a different k.

Passing it would suggest a third free dimension and invite a 100 × 100 × 200 table — mostly unreachable states. Deriving it keeps the state space at 101 × 101.

"Why is it exponential?"

Two branches whenever both strings match, so up to 2^(m+n) paths over only m × n distinct (i, j) states. At m = n = 100 that's 2^200 versus 10^4.

Approach 2 — 2-D tabulation (optimal)

public boolean isInterleave(String s1, String s2, String s3) {
    int m = s1.length(), n = s2.length();
    if (m + n != s3.length()) return false;          // O(1) rejection

    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;

    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= n; j++) {
            if (i > 0 && dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                dp[i][j] = true;
            if (j > 0 && dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1))
                dp[i][j] = true;
        }

    return dp[m][n];
}

Trace — s1 = "ab", s2 = "cd", s3 = "acbd":

dp[2][2] = true ✓ — a c b d

• Time O(m · n) · Space O(m · n)

Counter-questions on this approach

⭐ "Why is s3.charAt(i + j - 1) the character being matched?"

Because dp[i][j] concerns s3's first i + j characters, whose last one is at index i + j − 1.

It's the same prefix-length-versus-position offset as everywhere: dp is indexed by counts, strings by positions.

⭐ "Why is the length check required rather than just fast?"

Without it, s3.charAt(i + j - 1) can index past the end when s3 is shorter than m + n, throwing StringIndexOutOfBoundsException.

And when s3 is longer, the table would report true for a prefix match while the tail is unexamined — a wrong answer rather than a crash. So it guards both failure modes.

⭐ "Why does the loop start at i = 0, j = 0 rather than 1?"

Because row 0 and column 0 need filling too. dp[0][j] asks whether s2's first j characters match s3's first j — a genuine computation, not a constant.

The i > 0 and j > 0 guards inside prevent the negative indexing at the origin, where dp[0][0] is already seeded.

"Why are both conditions if rather than else if?"

Because either route may succeed independently, and dp[i][j] should be true if either works. Using else if would skip the second check when the first fails to set it, which is subtly different — actually with plain ifs the second can still set it after the first didn't, which is what's wanted.

Written as a single || expression it's equivalent and arguably clearer.

"Can this be rolled to one row?"

Yes. dp[i][j] reads only dp[i-1][j] (above) and dp[i][j-1] (left) — no diagonal — so a single array works with j ascending, exactly like Unique Paths.

That gives O(min(m,n)) space. I'd mention it; at 100 × 100 the full table is 10,000 booleans, so it isn't pressing.

Comparison

4. Why the Optimal Wins

The recursion re-explores (i, j) pairs exponentially often when only 10^4 exist.

The modelling insight is that the state is two indices, not three — k is determined by i + j. Recognising that redundancy is what keeps the table at 101 × 101 instead of 101 × 101 × 201.

The framing worth keeping:

Greedy fails when both strings offer the same next character, so both branches must be explored. The state is (i, j) and k = i + j is derived — noticing that dependency is what keeps it 2-D.

5. Java Prerequisites

The interleaving recurrence

dp[i][j] = (i > 0 && dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1))
        || (j > 0 && dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1));

Derived index — k = i + j, never stored.

Length check first — prevents both an out-of-bounds read and a false positive on a prefix.

Short-circuit && — the i > 0 guard must precede the indexing, or dp[-1][j] throws.

6. Interview Communication Guide

Clarifying questions: Must the relative order within each string be preserved (yes — that's what interleaving means)? Can either string be empty (yes, including all three)? Are characters case-sensitive (assume yes)? Must every character of both be used (yes — hence the length check)?

The pitch

"Greedy doesn't work here. At each step I take the next character of s3, and if only one of the two strings offers it the choice is forced — but if both do, there's no basis for choosing, and committing to one can dead-end. With s1 = 'aa', s2 = 'ab', s3 = 'aaab', the first a could come from either.

So both branches must be explored, which makes it a search — and the overlapping subproblems make it a DP.

The state is dp[i][j]: can s3's first i + j characters be formed from s1's first i and s2's first j?

The important modelling point is that k is derived, not tracked. If i characters come from s1 and j from s2, exactly i + j of s3 are consumed — there's no freedom. Tracking k separately would make it a 100 × 100 × 200 table with most states unreachable; deriving it keeps it 101 × 101.

The recurrence takes the next character from s1 or from s2, so it's an || — an existence question.

Before anything, I check s1.length + s2.length == s3.length. That's not just an optimisation: without it, s3.charAt(i + j - 1) can index past the end and throw, and a longer s3 would report true on a prefix match while the tail goes unexamined.

O(m · n) = 10^4 time and space. It can be rolled to one row, since the recurrence reads only above and left with no diagonal — unlike LCS, which needs two rows."

Edge cases to volunteer:

Name the all-empty case and the length mismatch. The first confirms dp[0][0] = true; the second is where a missing length check throws rather than returning false.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the interleaving pattern — which string each character came from."

Track the winning direction per cell and walk back from dp[m][n]. O(m·n) space, so the rolling optimisation is forfeited — the usual trade.

⭐ "Interleave three strings instead of two."

dp[i][j][k] with s4's index derived as i + j + k. O(n³) time and space. The shape generalises directly; the cost doesn't.

"Count the distinct interleavings rather than testing existence."

Change boolean to int and || to +. Same structure, counting combiner. Note that identical characters can make different paths produce the same string, so "distinct interleavings" and "distinct results" differ — worth clarifying which is meant.

"What if characters could be skipped?"

Then it's no longer interleaving — it becomes a subsequence-matching problem, closer to Distinct Subsequences. The length check disappears, and so does the derived k.

"What if m and n were 10^4?"

O(m·n) = 10^8 — borderline. The rolled version is O(min(m,n)) space, which helps memory but not time. There's no known sub-quadratic algorithm.

"Is there a greedy that works with a tie-break rule?"

No sound one. Any fixed rule can be defeated by constructing a case where the other choice was required — which is why the branching is essential rather than a failure of imagination.