Interleaving String

Interleaving String sounds easy until you try it. You take two strings and mix them together. The question is whether a third string is a valid mix. The trap is that a greedy left to right match fails. The interviewer wants to see if you can model this with a clean two-dimensional grid.

🎯 The Problem

You get three strings, s1, s2, and s3. Decide if s3 is formed by mixing s1 and s2.

The rules:

• Mixing means you keep the order of letters inside each string.
• You only interleave them. You never reorder letters within s1 or within s2.
• The length of s3 must equal the length of s1 plus the length of s2, or the answer is false right away.
• Return true or false.

For s1 = "aab", s2 = "axy", and s3 = "aaxaby", you can build s3 by taking letters in order from both. So the answer is true.

Input:  s1 = "aab", s2 = "axy", s3 = "aaxaby"
Output: true

Explanation: take a(s1) a(s1) x(s2) a... wait, build it as:
  a(s1) a(s2? no) ...
  One valid mix: a a x a b y
    s1 gives: a a b   (in order)
    s2 gives: a x y   (in order)
  Merged in order -> a a x a b y = s3

Here is the core choice at each step. To match the next letter of s3, it must come from either s1 or s2.

🐢 Approach 1: Try Both Sources (Brute Force)

The idea in one line: walk two pointers and try taking the next letter of s3 from s1 or from s2.

The idea:

• Pointer i is the position in s1. Pointer j is the position in s2.
• The position in s3 is always i + j, because together they have used i + j letters.

How it works:

• Look at the next letter of s3.
• If it equals the next letter of s1, try taking it from s1.
• If it equals the next letter of s2, try taking it from s2.
• If either path leads to a full match, the answer is true.

Why it is weak:

• At each step you may branch into two paths.
• With long strings the number of paths grows close to 2 to the power of the length.
• Far too slow.

Here is the plain recursion code:

def is_interleave(s1, s2, s3):
    if len(s1) + len(s2) != len(s3):
        return False

    def dfs(i, j):
        k = i + j
        if k == len(s3):
            return True
        take_s1 = i < len(s1) and s1[i] == s3[k] and dfs(i + 1, j)
        take_s2 = j < len(s2) and s2[j] == s3[k] and dfs(i, j + 1)
        return take_s1 or take_s2

    return dfs(0, 0)

🧠 Approach 2: Memoization (Better)

The idea in one line: cache the answer for each (i, j) pair so paths share work.

The idea:

• Both i and j can be reached by many different paths.
• But the answer for a given (i, j) pair never changes.

How it works:

• Store the answer for each (i, j) pair the first time you compute it.
• If you return to the same pair, read the saved answer.

Why it is fast:

• There are only about (length of s1 + 1) * (length of s2 + 1) pairs.
• The work is bounded by the size of that grid. This is memoization.

Here is the memoized recursion:

from functools import lru_cache


def is_interleave(s1, s2, s3):
    if len(s1) + len(s2) != len(s3):
        return False

    @lru_cache(None)
    def dfs(i, j):
        k = i + j
        if k == len(s3):
            return True
        return (
            i < len(s1) and s1[i] == s3[k] and dfs(i + 1, j)
        ) or (
            j < len(s2) and s2[j] == s3[k] and dfs(i, j + 1)
        )

    return dfs(0, 0)

🚀 Approach 3: 2D Boolean Table (Best)

The idea in one line: fill a grid where each cell is true if two prefixes interleave into a prefix of s3.

The idea:

• Make a table dp where dp[i][j] is true if the first i of s1 and first j of s2 form the first i + j of s3.
• The start dp[0][0] is true. Zero letters from each forms an empty string, matching the empty start of s3.

How it works:

• To reach dp[i][j], the last letter of the s3 prefix came from one of two places.
• It came from s1 if that letter equals the i-th letter of s1 and dp[i-1][j] was true.
• It came from s2 if that letter equals the j-th letter of s2 and dp[i][j-1] was true.
• If either works, dp[i][j] is true.

Why it is best:

• Each cell is filled once, so the time is O(n times m).
• No recursion. The answer is dp[len(s1)][len(s2)], whether all of s1 and all of s2 form all of s3.

Steps to Solve

1. If len(s1) + len(s2) is not len(s3), return false.
2. Make a dp table of size (len(s1)+1) by (len(s2)+1), all false.
3. Set dp[0][0] = true.
4. Fill the first row and column. They handle using letters from only one string.
5. For each cell, check the match from s1 (dp[i-1][j]) and the match from s2 (dp[i][j-1]).
6. Return the bottom-right cell dp[len(s1)][len(s2)].

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isInterleave(const char *s1, const char *s2, const char *s3) {
    int n = strlen(s1), m = strlen(s2);
    if (n + m != (int)strlen(s3)) return false;   // lengths must add up

    bool dp[101][101];
    dp[0][0] = true;                              // empty + empty = empty

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 && j == 0) continue;
            bool fromS1 = false, fromS2 = false;
            if (i > 0 && s1[i - 1] == s3[i + j - 1])
                fromS1 = dp[i - 1][j];            // last letter came from s1
            if (j > 0 && s2[j - 1] == s3[i + j - 1])
                fromS2 = dp[i][j - 1];            // last letter came from s2
            dp[i][j] = fromS1 || fromS2;
        }
    }
    return dp[n][m];
}

int main(void) {
    const char *s1 = "aab", *s2 = "axy", *s3 = "aaxaby";
    printf("%s\n", isInterleave(s1, s2, s3) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool isInterleave(string s1, string s2, string s3) {
    int n = s1.size(), m = s2.size();
    if (n + m != (int)s3.size()) return false;    // lengths must add up

    vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
    dp[0][0] = true;                              // empty + empty = empty

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 && j == 0) continue;
            bool fromS1 = false, fromS2 = false;
            if (i > 0 && s1[i - 1] == s3[i + j - 1])
                fromS1 = dp[i - 1][j];            // came from s1
            if (j > 0 && s2[j - 1] == s3[i + j - 1])
                fromS2 = dp[i][j - 1];            // came from s2
            dp[i][j] = fromS1 || fromS2;
        }
    }
    return dp[n][m];
}

int main() {
    cout << (isInterleave("aab", "axy", "aaxaby") ? "true" : "false") << endl;
    return 0;
}

true

public class InterleavingString {
    public static boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length();
        if (n + m != s3.length()) return false;   // lengths must add up

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

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i == 0 && j == 0) continue;
                boolean fromS1 = false, fromS2 = false;
                if (i > 0 && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                    fromS1 = dp[i - 1][j];        // came from s1
                if (j > 0 && s2.charAt(j - 1) == s3.charAt(i + j - 1))
                    fromS2 = dp[i][j - 1];        // came from s2
                dp[i][j] = fromS1 || fromS2;
            }
        }
        return dp[n][m];
    }

    public static void main(String[] args) {
        System.out.println(isInterleave("aab", "axy", "aaxaby"));
    }
}

true

def is_interleave(s1, s2, s3):
    n, m = len(s1), len(s2)
    if n + m != len(s3):              # lengths must add up
        return False

    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True                  # empty + empty = empty

    for i in range(n + 1):
        for j in range(m + 1):
            if i == 0 and j == 0:
                continue
            from_s1 = False
            from_s2 = False
            if i > 0 and s1[i - 1] == s3[i + j - 1]:
                from_s1 = dp[i - 1][j]   # last letter came from s1
            if j > 0 and s2[j - 1] == s3[i + j - 1]:
                from_s2 = dp[i][j - 1]   # last letter came from s2
            dp[i][j] = from_s1 or from_s2

    return dp[n][m]


print(is_interleave("aab", "axy", "aaxaby"))

True

function isInterleave(s1, s2, s3) {
  const n = s1.length, m = s2.length;
  if (n + m !== s3.length) return false;   // lengths must add up

  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(false));
  dp[0][0] = true;                         // empty + empty = empty

  for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= m; j++) {
      if (i === 0 && j === 0) continue;
      let fromS1 = false, fromS2 = false;
      if (i > 0 && s1[i - 1] === s3[i + j - 1]) fromS1 = dp[i - 1][j];
      if (j > 0 && s2[j - 1] === s3[i + j - 1]) fromS2 = dp[i][j - 1];
      dp[i][j] = fromS1 || fromS2;
    }
  }
  return dp[n][m];
}

console.log(isInterleave("aab", "axy", "aaxaby"));

true

Let us walk through the Python version line by line. The grid is the whole idea.

n, m = len(s1), len(s2)
if n + m != len(s3):
    return False

We grab the lengths. If s1 and s2 together do not have the same number of letters as s3, no mix is possible. We stop right away.

dp = [[False] * (m + 1) for _ in range(n + 1)]
dp[0][0] = True

We make a grid with one extra row and one extra column. The extra slots stand for using zero letters. Here dp[i][j] means the first i letters of s1 and the first j letters of s2 form the first i + j letters of s3. We set dp[0][0] to True. Using nothing from each makes an empty string, which matches the empty start.

for i in range(n + 1):
    for j in range(m + 1):
        if i == 0 and j == 0:
            continue

We visit every cell. We skip the start cell because we already set it.

        if i > 0 and s1[i - 1] == s3[i + j - 1]:
            from_s1 = dp[i - 1][j]

This asks: could the last matched letter have come from s1? It can only come from s1 if the i-th letter of s1 equals the current letter of s3. And the smaller problem dp[i-1][j] must already be true. Note s3[i + j - 1] is the current letter, because i + j letters are used so far.

        if j > 0 and s2[j - 1] == s3[i + j - 1]:
            from_s2 = dp[i][j - 1]

The mirror case. The last letter could have come from s2 if its letter matches and dp[i][j-1] was true.

        dp[i][j] = from_s1 or from_s2

The cell is true if either source could supply the last letter. We only need one valid path.

return dp[n][m]

The bottom-right cell answers the full question. Can all of s1 and all of s2 interleave into all of s3?

Here is the filled grid for our example. A T means that cell is reachable. The bottom-right T is the answer.

⏱️ Time and Space Complexity

Recursion can branch twice at each step, so it is O(2^(n+m)) time. Memoization and the 2D table both visit each (i, j) cell once. There are (n+1) * (m+1) cells. So both are O(n * m) time. The table uses O(n * m) space, but you can shrink it to one row if you want. Here n is the length of s1 and m is the length of s2.

🧩 Key Takeaways

• ✅ The position in s3 is always i + j, so you only track two pointers.
• ✅ dp[i][j] is true if the first i of s1 and first j of s2 form the first i + j of s3.
• ✅ A cell is true if the last letter could come from s1 or from s2.
• ✅ A greedy left to right match fails. The grid keeps both choices open.
• ✅ The answer sits in the bottom-right cell dp[len(s1)][len(s2)].

🚀 What’s Next?

• Distinct Subsequences
• Target Sum