Interleaving String

MediumString DP · 2-D Grid Path🧩 String DP LeetCode #97 ↗Updated Oct 30, 2026

Problem

Given strings s1, s2 and s3, decide whether s3 can be built by merging s1 and s2 — using every character of both exactly once while keeping each string's own left-to-right order (like riffle-shuffling two decks).

Inputs1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"Outputtrue

Inputs1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"Outputfalse

Inputs1 = "", s2 = "", s3 = ""Outputtrue

0 ≤ s1.length, s2.length ≤ 100 · 0 ≤ s3.length ≤ 200 · lowercase letters · Follow-up: use only O(s2.length) extra memory.

Try it yourself

Java

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Once you have used i chars of s1 and j of s2, you are at position i+j of s3 — so the whole state is just the pair (i, j). It is a right/down path search on an (m+1)×(n+1) grid.

PatternString DP

Instinct Two strings compared char by char (match, edit, interleave) means dp[i][j] over prefixes; one string's palindromes or splits means dp[l][r] or dp[i].

Memory hack Match? Go diagonal. Mismatch? Ask the neighbours. Up drops a char from s, left drops one from t, diagonal uses both.

Open the String DP guide →

Approaches

Brute ForceRecursion — Take from s1 or s2

Time O(2^m+n)Space O(m+n)

At state (i, j) the next char of s3 must come from s1[i] or s2[j]. Try each one that matches and recurse. A length check up front rules out impossible inputs immediately.

Java

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

private boolean go(String s1, String s2, String s3, int i, int j) {
    if (i == s1.length() && j == s2.length()) return true;
    int k = i + j; // next position in s3
    if (i < s1.length() && s1.charAt(i) == s3.charAt(k) && go(s1, s2, s3, i + 1, j)) {
        return true;
    }
    return j < s2.length() && s2.charAt(j) == s3.charAt(k) && go(s1, s2, s3, i, j + 1);
}

Simple, but when both strings share letters it branches twice at every step.

BetterTop-Down Memoisation

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

The recursion only ever visits (m+1)(n+1) distinct states. Cache each state's result in a Boolean[][] so every (i, j) is solved once; repeated dead ends are answered instantly.

Java

private Boolean[][] memo;

public boolean isInterleave(String s1, String s2, String s3) {
    if (s1.length() + s2.length() != s3.length()) return false;
    memo = new Boolean[s1.length() + 1][s2.length() + 1];
    return go(s1, s2, s3, 0, 0);
}

private boolean go(String s1, String s2, String s3, int i, int j) {
    if (i == s1.length() && j == s2.length()) return true;
    if (memo[i][j] != null) return memo[i][j];
    int k = i + j;
    boolean ok = (i < s1.length() && s1.charAt(i) == s3.charAt(k) && go(s1, s2, s3, i + 1, j))
            || (j < s2.length() && s2.charAt(j) == s3.charAt(k) && go(s1, s2, s3, i, j + 1));
    memo[i][j] = ok;
    return ok;
}

Polynomial with minimal change to the brute force; still O(m·n) memory.

OptimalBottom-Up DP on One Row

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

dp[i][j] = can the first i of s1 and j of s2 form the first i+j of s3. It is true if we arrive from above (last char from s1) or from the left (last char from s2). Row i needs only row i-1, so one array suffices: before update dp[j] is “above”, dp[j-1] is already “left”.

Java

public boolean isInterleave(String s1, String s2, String s3) {
    int m = s1.length(), n = s2.length();
    if (m + n != s3.length()) return false;
    boolean[] dp = new boolean[n + 1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 && j == 0) {
                dp[j] = true;
                continue;
            }
            char want = s3.charAt(i + j - 1);
            boolean fromS1 = i > 0 && dp[j] && s1.charAt(i - 1) == want;
            boolean fromS2 = j > 0 && dp[j - 1] && s2.charAt(j - 1) == want;
            dp[j] = fromS1 || fromS2;
        }
    }
    return dp[n];
}

Iterative, no recursion depth, and meets the O(s2.length) memory follow-up.

Pro tip

If s2 is longer, swap the two inputs first so the row has min(m, n) + 1 cells.

At a glance

Level	Approach	Time	Space
Brute Force	Recursion — Take from s1 or s2	`O(2^m+n)`	`O(m+n)`
Better	Top-Down Memoisation	`O(m·n)`	`O(m·n)`
Optimal	Bottom-Up DP on One Row	`O(m·n)`	`O(n)`

Common pitfalls

Skipping the length check — leads to index errors or false positives.
Greedy “take from s1 whenever it matches” fails when both strings offer the same letter.
Off-by-one: the s3 char for cell (i, j) is s3[i+j-1], not s3[i+j].

Interview tips

Point out that k = i + j is implied, so the state is only 2-D.
Show a quick counter-example where greedy breaks to justify DP.
Describe it as a path search on a grid: down = use s1, right = use s2.

Pattern

Two-pointer state DP → when two sequences are consumed in order and a third index is implied by them.

My notes saved in this browser