#97 Interleaving String

frequently reported atAmazon Microsoft Google

the problem

In plain words

Decide whether s3 can be built by merging s1 and s2 letter by letter, keeping the letters of s1 in their original order and the letters of s2 in theirs. Every letter of s1 and of s2 must be used exactly once.

in s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

out true

aa (s1) + dbbc (s2) + bc (s1) + a (s2) + c (s1).

in s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

out false

in s1 = "", s2 = "", s3 = ""

out true

0 ≤ s1.length, s2.length ≤ 100
0 ≤ s3.length ≤ 200
Lowercase English letters
Follow-up: O(s2.length) extra memory

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

pattern2D DP on two strings (LCS / edit distance)

After using i letters of s1 and j letters of s2 you have built exactly the first i + j letters of s3. The last of them came either from s1 (↑ in the table) or from s2 (←). So dp[i][j] = (s1[i − 1] == s3[i + j − 1] && dp[i − 1][j]) || (s2[j − 1] == s3[i + j − 1] && dp[i][j − 1]).

solutions

From brute force to optimal

can(i, j): s3's next letter must come from s1[i] or s2[j]; try both when both fit.

Lengths don't add up → false.
i + j == s3.length → true.
Try s1 if it fits, then s2 if it fits.

timeO(2^(m+n))

When both strings offer the same letter, both branches are explored, at every step.

spaceO(m + n)

Recursion depth.

javajava.util.*

1class Solution {2    public boolean isInterleave(String s1, String s2, String s3) {3        if (s1.length() + s2.length() != s3.length()) return false;4        return can(s1, s2, s3, 0, 0);5    }6 7    /** Can s1[i..] and s2[j..] interleave into s3[i + j..]? */8    private boolean can(String s1, String s2, String s3, int i, int j) {9        if (i + j == s3.length()) return true;10        char c = s3.charAt(i + j);11        return (i < s1.length() && s1.charAt(i) == c && can(s1, s2, s3, i + 1, j))  // next char came from s112            || (j < s2.length() && s2.charAt(j) == c && can(s1, s2, s3, i, j + 1)); // or from s213    }14}

Only (m + 1)(n + 1) pairs: cache them in a Boolean[][].

null = unknown; check, compute, store.

timeO(m·n)

Each pair once, O(1) work.

spaceO(m·n)

Memo + O(m + n) stack.

javajava.util.*

1class Solution {2    public boolean isInterleave(String s1, String s2, String s3) {3        if (s1.length() + s2.length() != s3.length()) return false;4        return can(s1, s2, s3, 0, 0, new Boolean[s1.length() + 1][s2.length() + 1]); // null = unknown5    }6 7    private boolean can(String s1, String s2, String s3, int i, int j, Boolean[][] memo) {8        if (i + j == s3.length()) return true;9        if (memo[i][j] != null) return memo[i][j];10        char c = s3.charAt(i + j);11        boolean ok = (i < s1.length() && s1.charAt(i) == c && can(s1, s2, s3, i + 1, j, memo))12                  || (j < s2.length() && s2.charAt(j) == c && can(s1, s2, s3, i, j + 1, memo));13        return memo[i][j] = ok;14    }15}

Fill dp[i][j] row by row with the ↑ / ← rule.

dp[0][0] = true.
From s1: dp[i − 1][j] and the letters match. From s2: dp[i][j − 1] and the letters match.
Return dp[m][n].

timeO(m·n)

One O(1) step per cell.

spaceO(m·n)

The (m + 1) × (n + 1) table.

javajava.util.*

1class Solution {2    public boolean isInterleave(String s1, String s2, String s3) {3        int m = s1.length(), n = s2.length();4        if (m + n != s3.length()) return false;5        boolean[][] dp = new boolean[m + 1][n + 1]; // dp[i][j]: s1[0..i) + s2[0..j) can make s3[0..i+j)6        dp[0][0] = true;7        for (int i = 0; i <= m; i++) {8            for (int j = 0; j <= n; j++) {9                if (i > 0 && s1.charAt(i - 1) == s3.charAt(i + j - 1)) dp[i][j] |= dp[i - 1][j]; // last char from s110                if (j > 0 && s2.charAt(j - 1) == s3.charAt(i + j - 1)) dp[i][j] |= dp[i][j - 1]; // last char from s211            }12        }13        return dp[m][n];14    }15}

A cell reads only up (old dp[j]) and left (new dp[j − 1]), so one array of n + 1 booleans is enough.

Length check first.
For i = 0..m, for j = 0..n: dp[j] = (i > 0 && dp[j] && s1 fits) || (j > 0 && dp[j − 1] && s2 fits).
Return dp[n].

timeO(m·n)

Same cells as the table.

spaceO(n)

One row of n + 1 booleans — the follow-up asks for exactly this.

javajava.util.*

1class Solution {2    public boolean isInterleave(String s1, String s2, String s3) {3        int m = s1.length(), n = s2.length();4        if (m + n != s3.length()) return false; // every char must be used exactly once5        boolean[] dp = new boolean[n + 1]; // dp[j]: row i of the table, overwritten row by row6        for (int i = 0; i <= m; i++) {7            for (int j = 0; j <= n; j++) {8                if (i == 0 && j == 0) { dp[0] = true; continue; } // nothing used, nothing made9                char c = s3.charAt(i + j - 1); // the char that cell (i, j) must explain10                boolean fromS1 = i > 0 && dp[j] && s1.charAt(i - 1) == c;         // dp[j] still holds row i - 111                boolean fromS2 = j > 0 && dp[j - 1] && s2.charAt(j - 1) == c;     // dp[j - 1] is already row i12                dp[j] = fromS1 || fromS2;13            }14        }15        return dp[n];16    }17}

sim

One row, overwritten row by row

loading simulation…

javajava.util.*

1class Solution {2    public boolean isInterleave(String s1, String s2, String s3) {3        int m = s1.length(), n = s2.length();4        if (m + n != s3.length()) return false; // every char must be used exactly once5        boolean[] dp = new boolean[n + 1]; // dp[j]: row i of the table, overwritten row by row6        for (int i = 0; i <= m; i++) {7            for (int j = 0; j <= n; j++) {8                if (i == 0 && j == 0) { dp[0] = true; continue; } // nothing used, nothing made9                char c = s3.charAt(i + j - 1); // the char that cell (i, j) must explain10                boolean fromS1 = i > 0 && dp[j] && s1.charAt(i - 1) == c;         // dp[j] still holds row i - 111                boolean fromS2 = j > 0 && dp[j - 1] && s2.charAt(j - 1) == c;     // dp[j - 1] is already row i12                dp[j] = fromS1 || fromS2;13            }14        }15        return dp[n];16    }17}

in the room

How to say it in the interview

talk track

Kill greedy first: "take from s1 whenever it matches" fails on s1 = "aa", s2 = "ab", s3 = "aaba".
State: "dp[i][j] = can the first i of s1 and the first j of s2 build the first i + j of s3?"
Then the follow-up: one row, because each cell reads up (the old dp[j]) and left (the new dp[j − 1]).

traps

Skipping the length check: s3 may have leftover letters.
Greedy matching when both strings offer the same letter — both branches must be explored.
Off by one: cell (i, j) explains s3[i + j − 1], not s3[i + j].

what they ask next

Follow-ups

Return one valid merge?

Keep the full table and walk back from (m, n): step up when the letter came from s1, left when it came from s2 (that's the green path in the sim).

Three strings to merge into a fourth?

dp[i][j][k] with the same rule over three prefixes: O(a·b·c).

before you submit

Edge cases to test

Lengths don't add up → false at once.
All three empty → true; one empty → s3 must equal the other.
Both strings offer the same letter: s1 = "aa", s2 = "ab", s3 = "aaba" → true, but greedy-from-s1 gets stuck.

practise next