Find if a string is interleaved of two other strings

Problem Statement

Given three strings s1, s2, and s3, determine whether s3 is formed by an interleaving of s1 and s2. An interleaving of two strings is formed by merging them while maintaining the relative order of characters in each string.

Example:

• Input: s1 = "aab", s2 = "axy", s3 = "aaxaby"

• Output: true

• Explanation: s3 = "a(a)x(a)b(y)" where characters from s1 are in parentheses: a_a_b interleaved with a_x_y gives aaxaby.

• Input: s1 = "aab", s2 = "axy", s3 = "abaaxy"

• Output: false

Noob-Friendly Explanation

Imagine you have two decks of cards. You want to merge them into one pile by picking cards from either deck, one at a time, but you must keep the order of each deck. The question is: can you merge the two decks to form a specific target pile?

For example, deck 1 = [a, a, b] and deck 2 = [a, x, y]. If the target pile is [a, a, x, a, b, y], you pick: deck1, deck1, deck2, deck1, deck1 — wait, that doesn't work. But [a, a, x, a, b, y] can be formed as: a(d1), a(d2), x(d2), a(d1), b(d1), y(d2). Yes!

Approach 1: Brute Force (Recursion)

Intuition

At each position in s3, we decide: does this character come from s1 or s2? Try both options recursively.

Algorithm

1. Use three pointers: i for s1, j for s2, k for s3.
2. If s3[k] == s1[i], try advancing both i and k.
3. If s3[k] == s2[j], try advancing both j and k.
4. If we reach the end of s3 with i and j also at their ends, return true.

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

    private boolean solve(String s1, String s2, String s3, int i, int j, int k) {
        if (k == s3.length()) {
            return i == s1.length() && j == s2.length();
        }

        boolean result = false;

        // Try taking from s1
        if (i < s1.length() && s1.charAt(i) == s3.charAt(k)) {
            result = solve(s1, s2, s3, i + 1, j, k + 1);
        }

        // Try taking from s2
        if (!result && j < s2.length() && s2.charAt(j) == s3.charAt(k)) {
            result = solve(s1, s2, s3, i, j + 1, k + 1);
        }

        return result;
    }
}

Complexity Analysis

• Time Complexity: O(2^(m+n)) - At each step, we can branch into two choices.
• Space Complexity: O(m+n) - Recursion stack depth.

Approach 2: Optimal (Dynamic Programming)

Intuition

Use a 2D DP table where dp[i][j] = true if s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1].

Algorithm

1. If lengths don't add up, return false.
2. dp[0][0] = true (empty strings interleave to empty string).
3. Fill first row: dp[0][j] = true if s2's first j characters match s3's first j characters.
4. Fill first column similarly for s1.
5. For each dp[i][j]: check if taking from s1 (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or from s2 (dp[i][j-1] and s2[j-1] == s3[i+j-1]) works.

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[m + 1][n + 1];
        dp[0][0] = true;

        // Fill first row (only using s2)
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }

        // Fill first column (only using s1)
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        }

        // Fill rest of the table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                boolean fromS1 = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
                boolean fromS2 = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
                dp[i][j] = fromS1 || fromS2;
            }
        }

        return dp[m][n];
    }
}

Complexity Analysis

• Time Complexity: O(m*n) - We fill an (m+1)×(n+1) table.
• Space Complexity: O(m*n) - For the 2D DP table.