Interleaving String

MediumDynamic Programming (1-D & 2-D)NeetCode 150MidOpen on LeetCodeUpdated Nov 11, 2026

You're given three strings s1, s2, and s3. Return true if s3 can be formed by interleaving s1 and s2: splitting each into pieces and merging the pieces so that the characters of s1 keep their order, the characters of s2 keep their order, and every character of both is used exactly once.

Examples

s1 = "ab", s2 = "cd", s3 = "acbd" returns true

Take a from s1, c from s2, b from s1, and d from s2.

s1 = "ab", s2 = "cd", s3 = "adcb" returns false

s3 puts d before c, but s2 must keep c ahead of d.

s1 = "aa", s2 = "ab", s3 = "aaba" returns true

Take a from s1, then a and b from s2, then the last a from s1. Greedy choices fail here, since three strings start with a.

Constraints

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
The strings consist of lowercase English letters.

Hints

Hint 1

At each step, the next character of s3 has to come from the front of what's left of s1 or of s2. When can both be possible?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Let dp[i][j] be true when the first i characters of s1 and the first j of s2 can interleave into the first i + j characters of s3. dp[0][0] is true. dp[i][j] holds if dp[i - 1][j] holds and s1[i - 1] matches s3[i + j - 1], or if dp[i][j - 1] holds and s2[j - 1] matches it. Check first that the lengths add up. Each row depends only on itself and the row above, so one array of length n + 1 is enough. O(m * n) time, O(n) space.

Time

O(m * n)

Space

O(n)

Pitfall

Taking a character from whichever string matches first. When both s1 and s2 can supply the next character, either choice may be the only one that works, so the decision has to be tried both ways, which is what the table does.

Solutions

class Solution {
    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 target = s3.charAt(i + j - 1);
                boolean fromS1 = i > 0 && dp[j] && s1.charAt(i - 1) == target;
                boolean fromS2 = j > 0 && dp[j - 1] && s2.charAt(j - 1) == target;
                dp[j] = fromS1 || fromS2;
            }
        }
        return dp[n];
    }
}

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        dp = [False] * (n + 1)
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 and j == 0:
                    dp[j] = True
                    continue
                target = s3[i + j - 1]
                from_s1 = i > 0 and dp[j] and s1[i - 1] == target
                from_s2 = j > 0 and dp[j - 1] and s2[j - 1] == target
                dp[j] = from_s1 or from_s2
        return dp[n]