Interleaving String

🎯

Interleaving String

hardDPGoogleAmazon

Imagine you have two different messages and want to combine them into one without changing the order of characters in either message. Can you verify if a given combined message is a valid interleaving of the two?

💡 This problem tests your understanding of how two sequences can be merged while preserving their individual order. Beginners often struggle because it requires checking multiple overlapping possibilities, which is not straightforward without dynamic programming.

📋

Problem Statement

Given three strings s1, s2, and s3, determine if s3 is formed by an interleaving of s1 and s2. An interleaving of two strings s and t is a string that contains all characters of s and t and preserves the left-to-right order of characters from each string.

1 ≤ len(s1), len(s2) ≤ 10^5len(s3) = len(s1) + len(s2)s1, s2, s3 consist of lowercase English letters

💡

Example

Input"s1 = 'aabcc', s2 = 'dbbca', s3 = 'aadbbcbcac'"

Outputtrue

s3 can be formed by interleaving s1 and s2 preserving order.

Input"s1 = 'aabcc', s2 = 'dbbca', s3 = 'aadbbbaccc'"

Outputfalse

s3 cannot be formed by interleaving s1 and s2.

• Empty s1 and s2, s3 is empty → true
• s3 length not equal to sum of s1 and s2 lengths → false
• All characters same in s1 and s2 → test order preservation
• One string empty, s3 equals the other string → true

🔁

Why DP?

Why greedy fails:

A greedy approach might try to match characters from s3 with s1 or s2 as they appear, but this fails when multiple choices exist. For example, s1='aab', s2='axy', s3='aaxaby' - greedily choosing from s1 first can lead to incorrect rejection.

DP state:

dp[i][j] means whether s3[:i+j] can be formed by interleaving s1[:i] and s2[:j].

Recurrence:dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])

We can form s3 up to i+j if either s1's last char matches s3 and previous dp state was true, or s2's last char matches s3 and previous dp state was true.

⚠️

Common Mistakes

Not checking length equality of s3 with s1 + s2

Incorrectly returns true or runs unnecessary computations

✅ Add early length check before DP or recursion

Overwriting dp array values in wrong order in space optimized approach

Incorrect dp results due to corrupted states

✅ Iterate dp array backwards when updating

Forgetting to memoize recursive calls

Exponential time leading to TLE

✅ Use a memo dictionary or map keyed by indices

Incorrect indexing when comparing characters (off-by-one errors)

Wrong results or runtime errors

✅ Carefully use i-1, j-1 for s1, s2 and i+j-1 for s3 indexing

Not handling empty strings properly in base cases

Fails on edge cases with empty inputs

✅ Initialize dp[0][0] = True and fill first row/column accordingly

🧠

Brute Force (Pure Recursion)

💡 This approach helps understand the problem's recursive structure and why naive solutions are inefficient due to repeated work.

Intuition

Try all ways to pick characters from s1 or s2 to match s3, recursively checking both possibilities at each step.

Algorithm

1. Start from indices i, j at 0 for s1 and s2 respectively.
2. If current s3 character matches s1[i], recurse by incrementing i.
3. If current s3 character matches s2[j], recurse by incrementing j.
4. Return true if end of s3 is reached; false if no match.

💡 The recursion tree grows exponentially because both choices are explored at each step without caching.

Recurrence:dp(i,j) = (s1[i] == s3[i+j] and dp(i+1,j)) or (s2[j] == s3[i+j] and dp(i,j+1))

</>

Code

def isInterleave(s1, s2, s3):
    def dfs(i, j):
        if i == len(s1) and j == len(s2):
            return True
        if i < len(s1) and s1[i] == s3[i+j]:
            if dfs(i+1, j):
                return True
        if j < len(s2) and s2[j] == s3[i+j]:
            if dfs(i, j+1):
                return True
        return False
    if len(s1) + len(s2) != len(s3):
        return False
    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    print(isInterleave('aabcc', 'dbbca', 'aadbbcbcac'))  # True
    print(isInterleave('aabcc', 'dbbca', 'aadbbbaccc'))  # False

Line Notes

def dfs(i, j):Defines recursive helper to check interleaving from indices i, j

if i == len(s1) and j == len(s2):Base case: all characters matched

if i < len(s1) and s1[i] == s3[i+j]:Try taking character from s1 if it matches s3

if dfs(i+1, j):If taking from s1 leads to solution, return True

if j < len(s2) and s2[j] == s3[i+j]:Try taking character from s2 if it matches s3

if dfs(i, j+1):If taking from s2 leads to solution, return True

return FalseNo valid interleaving found from this path

if len(s1) + len(s2) != len(s3):Quick length check to avoid unnecessary recursion

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        return dfs(s1, 0, s2, 0, s3);
    }
    private boolean dfs(String s1, int i, String s2, int j, String s3) {
        if (i == s1.length() && j == s2.length()) return true;
        if (i < s1.length() && s1.charAt(i) == s3.charAt(i + j)) {
            if (dfs(s1, i + 1, s2, j, s3)) return true;
        }
        if (j < s2.length() && s2.charAt(j) == s3.charAt(i + j)) {
            if (dfs(s1, i, s2, j + 1, s3)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbcbcac")); // true
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbbaccc")); // false
    }
}

Line Notes

if (s1.length() + s2.length() != s3.length()) return false;Length mismatch means no interleaving possible

private boolean dfs(String s1, int i, String s2, int j, String s3)Recursive helper to explore interleaving

if (i == s1.length() && j == s2.length()) return true;Base case: all characters matched

if (i < s1.length() && s1.charAt(i) == s3.charAt(i + j))Try taking character from s1 if matches s3

if (dfs(s1, i + 1, s2, j, s3)) return true;Return true if path from s1 leads to solution

if (j < s2.length() && s2.charAt(j) == s3.charAt(i + j))Try taking character from s2 if matches s3

if (dfs(s1, i, s2, j + 1, s3)) return true;Return true if path from s2 leads to solution

return false;No valid interleaving found

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

class Solution {
public:
    bool dfs(const string& s1, int i, const string& s2, int j, const string& s3) {
        if (i == s1.size() && j == s2.size()) return true;
        if (i < s1.size() && s1[i] == s3[i + j]) {
            if (dfs(s1, i + 1, s2, j, s3)) return true;
        }
        if (j < s2.size() && s2[j] == s3[i + j]) {
            if (dfs(s1, i, s2, j + 1, s3)) return true;
        }
        return false;
    }
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        return dfs(s1, 0, s2, 0, s3);
    }
};

int main() {
    Solution sol;
    cout << boolalpha << sol.isInterleave("aabcc", "dbbca", "aadbbcbcac") << endl; // true
    cout << boolalpha << sol.isInterleave("aabcc", "dbbca", "aadbbbaccc") << endl; // false
    return 0;
}

Line Notes

bool dfs(const string& s1, int i, const string& s2, int j, const string& s3)Recursive helper to check interleaving from indices i, j

if (i == s1.size() && j == s2.size()) return true;Base case: all characters matched

if (i < s1.size() && s1[i] == s3[i + j])Try taking character from s1 if matches s3

if (dfs(s1, i + 1, s2, j, s3)) return true;Return true if path from s1 leads to solution

if (j < s2.size() && s2[j] == s3[i + j])Try taking character from s2 if matches s3

if (dfs(s1, i, s2, j + 1, s3)) return true;Return true if path from s2 leads to solution

if (s1.size() + s2.size() != s3.size()) return false;Length mismatch check

return dfs(s1, 0, s2, 0, s3);Start recursion from beginning

function isInterleave(s1, s2, s3) {
    if (s1.length + s2.length !== s3.length) return false;
    function dfs(i, j) {
        if (i === s1.length && j === s2.length) return true;
        if (i < s1.length && s1[i] === s3[i + j]) {
            if (dfs(i + 1, j)) return true;
        }
        if (j < s2.length && s2[j] === s3[i + j]) {
            if (dfs(i, j + 1)) return true;
        }
        return false;
    }
    return dfs(0, 0);
}

console.log(isInterleave('aabcc', 'dbbca', 'aadbbcbcac')); // true
console.log(isInterleave('aabcc', 'dbbca', 'aadbbbaccc')); // false

Line Notes

if (s1.length + s2.length !== s3.length) return false;Quick length check to avoid unnecessary recursion

function dfs(i, j) {Recursive helper to check interleaving from indices i, j

if (i === s1.length && j === s2.length) return true;Base case: all characters matched

if (i < s1.length && s1[i] === s3[i + j]) {Try taking character from s1 if matches s3

if (dfs(i + 1, j)) return true;Return true if path from s1 leads to solution

if (j < s2.length && s2[j] === s3[i + j]) {Try taking character from s2 if matches s3

if (dfs(i, j + 1)) return true;Return true if path from s2 leads to solution

return false;No valid interleaving found

⏱

Complexity

TimeO(2^(m+n))

SpaceO(m+n) due to recursion stack

At each step, two recursive calls may be made, leading to exponential time.

💡 For strings of length 20, this approach may do over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's recursive nature.

🧠

Top-Down DP with Memoization

💡 Memoization avoids repeated work by caching results of subproblems, making the recursive approach efficient.

Intuition

Store results of dfs(i,j) calls so that repeated states are computed once, reducing exponential to polynomial time.

Algorithm

1. Initialize a memo dictionary to store results for (i,j).
2. Perform recursive dfs with memo checks before computing.
3. Return cached result if available to avoid recomputation.
4. Combine results from taking characters from s1 or s2.

💡 Memoization transforms exponential recursion into polynomial by pruning repeated calls.

Recurrence:dp(i,j) = (s1[i] == s3[i+j] and dp(i+1,j)) or (s2[j] == s3[i+j] and dp(i,j+1))

</>

Code

def isInterleave(s1, s2, s3):
    memo = {}
    def dfs(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if i == len(s1) and j == len(s2):
            return True
        if i < len(s1) and s1[i] == s3[i+j]:
            if dfs(i+1, j):
                memo[(i, j)] = True
                return True
        if j < len(s2) and s2[j] == s3[i+j]:
            if dfs(i, j+1):
                memo[(i, j)] = True
                return True
        memo[(i, j)] = False
        return False
    if len(s1) + len(s2) != len(s3):
        return False
    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    print(isInterleave('aabcc', 'dbbca', 'aadbbcbcac'))  # True
    print(isInterleave('aabcc', 'dbbca', 'aadbbbaccc'))  # False

Line Notes

memo = {}Initialize cache to store results of subproblems

if (i, j) in memo:Return cached result if available to avoid recomputation

memo[(i, j)] = TrueCache positive result for current state

memo[(i, j)] = FalseCache negative result to prune future calls

if len(s1) + len(s2) != len(s3):Length check to quickly reject invalid inputs

import java.util.*;
public class Solution {
    private Map<String, Boolean> memo = new HashMap<>();
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        return dfs(s1, 0, s2, 0, s3);
    }
    private boolean dfs(String s1, int i, String s2, int j, String s3) {
        String key = i + "," + j;
        if (memo.containsKey(key)) return memo.get(key);
        if (i == s1.length() && j == s2.length()) return true;
        if (i < s1.length() && s1.charAt(i) == s3.charAt(i + j)) {
            if (dfs(s1, i + 1, s2, j, s3)) {
                memo.put(key, true);
                return true;
            }
        }
        if (j < s2.length() && s2.charAt(j) == s3.charAt(i + j)) {
            if (dfs(s1, i, s2, j + 1, s3)) {
                memo.put(key, true);
                return true;
            }
        }
        memo.put(key, false);
        return false;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbcbcac")); // true
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbbaccc")); // false
    }
}

Line Notes

private Map<String, Boolean> memo = new HashMap<>();Cache to store results of subproblems

String key = i + "," + j;Create unique key for memoization

if (memo.containsKey(key)) return memo.get(key);Return cached result if available

memo.put(key, true);Cache positive result

memo.put(key, false);Cache negative result

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

class Solution {
    unordered_map<string, bool> memo;
    bool dfs(const string& s1, int i, const string& s2, int j, const string& s3) {
        string key = to_string(i) + "," + to_string(j);
        if (memo.count(key)) return memo[key];
        if (i == s1.size() && j == s2.size()) return true;
        if (i < s1.size() && s1[i] == s3[i + j]) {
            if (dfs(s1, i + 1, s2, j, s3)) {
                memo[key] = true;
                return true;
            }
        }
        if (j < s2.size() && s2[j] == s3[i + j]) {
            if (dfs(s1, i, s2, j + 1, s3)) {
                memo[key] = true;
                return true;
            }
        }
        memo[key] = false;
        return false;
    }
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        return dfs(s1, 0, s2, 0, s3);
    }
};

int main() {
    Solution sol;
    cout << boolalpha << sol.isInterleave("aabcc", "dbbca", "aadbbcbcac") << endl; // true
    cout << boolalpha << sol.isInterleave("aabcc", "dbbca", "aadbbbaccc") << endl; // false
    return 0;
}

Line Notes

unordered_map<string, bool> memo;Cache to store results of subproblems

string key = to_string(i) + "," + to_string(j);Unique key for memoization

if (memo.count(key)) return memo[key];Return cached result if available

memo[key] = true;Cache positive result

memo[key] = false;Cache negative result

function isInterleave(s1, s2, s3) {
    if (s1.length + s2.length !== s3.length) return false;
    const memo = new Map();
    function dfs(i, j) {
        const key = i + ',' + j;
        if (memo.has(key)) return memo.get(key);
        if (i === s1.length && j === s2.length) return true;
        if (i < s1.length && s1[i] === s3[i + j]) {
            if (dfs(i + 1, j)) {
                memo.set(key, true);
                return true;
            }
        }
        if (j < s2.length && s2[j] === s3[i + j]) {
            if (dfs(i, j + 1)) {
                memo.set(key, true);
                return true;
            }
        }
        memo.set(key, false);
        return false;
    }
    return dfs(0, 0);
}

console.log(isInterleave('aabcc', 'dbbca', 'aadbbcbcac')); // true
console.log(isInterleave('aabcc', 'dbbca', 'aadbbbaccc')); // false

Line Notes

const memo = new Map();Cache to store results of subproblems

const key = i + ',' + j;Unique key for memoization

if (memo.has(key)) return memo.get(key);Return cached result if available

memo.set(key, true);Cache positive result

memo.set(key, false);Cache negative result

⏱

Complexity

TimeO(m*n)

SpaceO(m*n) due to memo and recursion stack

Each state (i,j) is computed once and cached, reducing exponential calls to polynomial.

💡 For strings of length 1000, this approach does about 1 million computations, which is feasible.

Interview Verdict: Accepted

Memoization makes the recursive solution efficient enough for large inputs.

🧠

Bottom-Up DP (Tabulation)

💡 This approach uses a 2D table to iteratively build solutions for smaller prefixes, avoiding recursion overhead.

Intuition

Build a dp table where dp[i][j] indicates if s3[:i+j] is interleaving of s1[:i] and s2[:j], filling row by row.

Algorithm

1. Initialize dp array of size (len(s1)+1) x (len(s2)+1) with False.
2. Set dp[0][0] = True as empty strings interleave to empty string.
3. Fill first row and first column based on matching prefixes.
4. Iterate over dp, setting dp[i][j] true if either dp[i-1][j] and s1[i-1] matches s3[i+j-1], or dp[i][j-1] and s2[j-1] matches s3[i+j-1].
5. Return dp[len(s1)][len(s2)] as final answer.

💡 The table systematically checks all prefix combinations, ensuring no state is missed or recomputed.

Recurrence:dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])

</>

Code

def isInterleave(s1, s2, s3):
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for i in range(1, m + 1):
        dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
    for j in range(1, n + 1):
        dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
    return dp[m][n]

# Example usage
if __name__ == '__main__':
    print(isInterleave('aabcc', 'dbbca', 'aadbbcbcac'))  # True
    print(isInterleave('aabcc', 'dbbca', 'aadbbbaccc'))  # False

Line Notes

dp = [[False] * (n + 1) for _ in range(m + 1)]Create 2D DP table initialized to False

dp[0][0] = TrueEmpty strings interleave to empty string

dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]Fill first column by matching s1 prefix with s3

dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]Fill first row by matching s2 prefix with s3

dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])Check if current dp state can be reached from top or left

public 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;
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) ||
                           (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbcbcac")); // true
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbbaccc")); // false
    }
}

Line Notes

boolean[][] dp = new boolean[m + 1][n + 1];Create 2D DP table initialized to false

dp[0][0] = true;Empty strings interleave to empty string

dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);Fill first column by matching s1 prefix with s3

dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);Fill first row by matching s2 prefix with s3

dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));Check if current dp state can be reached from top or left

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

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size();
        if (m + n != s3.size()) return false;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1];
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] && s2[j - 1] == s3[j - 1];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) ||
                           (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
            }
        }
        return dp[m][n];
    }
};

int main() {
    Solution sol;
    cout << boolalpha << sol.isInterleave("aabcc", "dbbca", "aadbbcbcac") << endl; // true
    cout << boolalpha << sol.isInterleave("aabcc", "dbbca", "aadbbbaccc") << endl; // false
    return 0;
}

Line Notes

vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));Create 2D DP table initialized to false

dp[0][0] = true;Empty strings interleave to empty string

dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1];Fill first column by matching s1 prefix with s3

dp[0][j] = dp[0][j - 1] && s2[j - 1] == s3[j - 1];Fill first row by matching s2 prefix with s3

dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);Check if current dp state can be reached from top or left

function isInterleave(s1, s2, s3) {
    const m = s1.length, n = s2.length;
    if (m + n !== s3.length) return false;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
    dp[0][0] = true;
    for (let i = 1; i <= m; i++) {
        dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];
    }
    for (let j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) ||
                       (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]);
        }
    }
    return dp[m][n];
}

console.log(isInterleave('aabcc', 'dbbca', 'aadbbcbcac')); // true
console.log(isInterleave('aabcc', 'dbbca', 'aadbbbaccc')); // false

Line Notes

const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));Create 2D DP table initialized to false

dp[0][0] = true;Empty strings interleave to empty string

dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];Fill first column by matching s1 prefix with s3

dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];Fill first row by matching s2 prefix with s3

dp[i][j] = (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]);Check if current dp state can be reached from top or left

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We fill a 2D table of size (m+1)*(n+1) once.

💡 For strings of length 1000, this means about 1 million table entries computed.

Interview Verdict: Accepted

Bottom-up DP is a standard, efficient approach for this problem.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i][j] depends only on dp[i-1][j] and dp[i][j-1], we can reduce space to one dimension.

Intuition

Use a 1D dp array representing the current row, updating it in place while iterating over s1 and s2.

Algorithm

1. Initialize a 1D dp array of size n+1 with False.
2. Set dp[0] = True for empty prefixes.
3. Fill dp for first row based on s2 prefix matching s3.
4. Iterate over s1 characters, updating dp from right to left for each s2 character.
5. Return dp[n] as final answer.

💡 Updating dp backwards ensures we don't overwrite values needed for current computation.

Recurrence:dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or (dp[j-1] and s2[j-1] == s3[i+j-1])

</>

Code

def isInterleave(s1, s2, s3):
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False
    dp = [False] * (n + 1)
    dp[0] = True
    for j in range(1, n + 1):
        dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]
    for i in range(1, m + 1):
        dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
        for j in range(n, 0, -1):
            dp[j] = (dp[j] and s1[i - 1] == s3[i + j - 1]) or (dp[j - 1] and s2[j - 1] == s3[i + j - 1])
    return dp[n]

# Example usage
if __name__ == '__main__':
    print(isInterleave('aabcc', 'dbbca', 'aadbbcbcac'))  # True
    print(isInterleave('aabcc', 'dbbca', 'aadbbbaccc'))  # False

Line Notes

dp = [False] * (n + 1)Initialize 1D dp array for s2 prefixes

dp[0] = TrueEmpty prefixes interleave to empty string

dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]Fill first row based on s2 prefix matching s3

dp[0] = dp[0] and s1[i - 1] == s3[i - 1]Update dp[0] for s1 prefix matching s3

for j in range(n, 0, -1):Iterate backwards to avoid overwriting needed dp values

dp[j] = (dp[j] and s1[i - 1] == s3[i + j - 1]) or (dp[j - 1] and s2[j - 1] == s3[i + j - 1])Update dp[j] based on previous states

public 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];
        dp[0] = true;
        for (int j = 1; j <= n; j++) {
            dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }
        for (int i = 1; i <= m; i++) {
            dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
            for (int j = n; j >= 1; j--) {
                dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) ||
                        (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbcbcac")); // true
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbbaccc")); // false
    }
}

Line Notes

boolean[] dp = new boolean[n + 1];Initialize 1D dp array for s2 prefixes

dp[0] = true;Empty prefixes interleave to empty string

dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);Fill first row based on s2 prefix matching s3

dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);Update dp[0] for s1 prefix matching s3

for (int j = n; j >= 1; j--)Iterate backwards to avoid overwriting needed dp values

dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));Update dp[j] based on previous states

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

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size();
        if (m + n != s3.size()) return false;
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int j = 1; j <= n; j++) {
            dp[j] = dp[j - 1] && s2[j - 1] == s3[j - 1];
        }
        for (int i = 1; i <= m; i++) {
            dp[0] = dp[0] && s1[i - 1] == s3[i - 1];
            for (int j = n; j >= 1; j--) {
                dp[j] = (dp[j] && s1[i - 1] == s3[i + j - 1]) ||
                        (dp[j - 1] && s2[j - 1] == s3[i + j - 1]);
            }
        }
        return dp[n];
    }
};

int main() {
    Solution sol;
    cout << boolalpha << sol.isInterleave("aabcc", "dbbca", "aadbbcbcac") << endl; // true
    cout << boolalpha << sol.isInterleave("aabcc", "dbbca", "aadbbbaccc") << endl; // false
    return 0;
}

Line Notes

vector<bool> dp(n + 1, false);Initialize 1D dp array for s2 prefixes

dp[0] = true;Empty prefixes interleave to empty string

dp[j] = dp[j - 1] && s2[j - 1] == s3[j - 1];Fill first row based on s2 prefix matching s3

dp[0] = dp[0] && s1[i - 1] == s3[i - 1];Update dp[0] for s1 prefix matching s3

for (int j = n; j >= 1; j--)Iterate backwards to avoid overwriting needed dp values

dp[j] = (dp[j] && s1[i - 1] == s3[i + j - 1]) || (dp[j - 1] && s2[j - 1] == s3[i + j - 1]);Update dp[j] based on previous states

function isInterleave(s1, s2, s3) {
    const m = s1.length, n = s2.length;
    if (m + n !== s3.length) return false;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
    for (let j = 1; j <= n; j++) {
        dp[j] = dp[j - 1] && s2[j - 1] === s3[j - 1];
    }
    for (let i = 1; i <= m; i++) {
        dp[0] = dp[0] && s1[i - 1] === s3[i - 1];
        for (let j = n; j >= 1; j--) {
            dp[j] = (dp[j] && s1[i - 1] === s3[i + j - 1]) ||
                    (dp[j - 1] && s2[j - 1] === s3[i + j - 1]);
        }
    }
    return dp[n];
}

console.log(isInterleave('aabcc', 'dbbca', 'aadbbcbcac')); // true
console.log(isInterleave('aabcc', 'dbbca', 'aadbbbaccc')); // false

Line Notes

const dp = new Array(n + 1).fill(false);Initialize 1D dp array for s2 prefixes

dp[0] = true;Empty prefixes interleave to empty string

dp[j] = dp[j - 1] && s2[j - 1] === s3[j - 1];Fill first row based on s2 prefix matching s3

dp[0] = dp[0] && s1[i - 1] === s3[i - 1];Update dp[0] for s1 prefix matching s3

for (let j = n; j >= 1; j--)Iterate backwards to avoid overwriting needed dp values

dp[j] = (dp[j] && s1[i - 1] === s3[i + j - 1]) || (dp[j - 1] && s2[j - 1] === s3[i + j - 1]);Update dp[j] based on previous states

⏱

Complexity

TimeO(m*n)

SpaceO(n)

We use a single dp array of size n+1 and update it for each character of s1.

💡 This reduces memory usage significantly while maintaining the same time complexity.

Interview Verdict: Accepted

Space optimization is a common follow-up and shows mastery of DP techniques.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoization or bottom-up DP are best for interviews; brute force is only for explanation; space optimized DP is a strong follow-up.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^(m+n))	O(m+n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down DP with Memoization	O(m*n)	O(m*n) memo + recursion stack	Possible but less likely	Yes	Good to code if comfortable with recursion
3. Bottom-Up DP (Tabulation)	O(m*n)	O(m*n)	No	Yes	Preferred approach to code
4. Space Optimized Bottom-Up DP	O(m*n)	O(n)	No	Yes, with extra bookkeeping	Good follow-up to discuss

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify input constraints and problem statement.Step 2: Describe brute force recursion to show understanding of problem structure.Step 3: Introduce memoization to optimize overlapping subproblems.Step 4: Present bottom-up DP for iterative solution.Step 5: Discuss space optimization if time permits.Step 6: Test with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to identify overlapping subproblems, implement DP correctly, optimize space, and handle edge cases.

Common Follow-ups

• What if s1 or s2 is empty? → Handle base cases carefully.
• Can you optimize space? → Use 1D DP array with backward iteration.

💡 These follow-ups test your understanding of base cases and space optimization, common in string DP problems.

🔍

Pattern Recognition

When to Use

1) Asked if one string is formed by interleaving two others; 2) Order of characters must be preserved; 3) Overlapping subproblems exist; 4) DP table can be formed over prefixes.

Signature Phrases

interleaving of two stringspreserving left-to-right orderformed by merging two sequences

NOT This Pattern When

Problems involving substring concatenation without order preservation or problems with only one string.

Similar Problems

Shuffle String - simpler rearrangement without order constraintsLongest Common Subsequence - related DP over two stringsDistinct Subsequences - counting ways to form a string from another

Practice

1. You are given two strings and want to find the minimum number of delete operations needed to make them equal. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming based on Longest Common Subsequence (LCS)

B. Greedy approach deleting mismatched characters as soon as found

C. Pure brute force recursion without memoization

D. Sorting both strings and comparing characters sequentially

Solution

1. Step 1: Understand problem requires minimal deletions to equalize strings

   This is equivalent to finding the longest common subsequence (LCS) and deleting characters not in it.

2. Step 2: Recognize DP approach based on LCS guarantees optimal solution

   Greedy or sorting approaches fail because they do not consider subsequence order; brute force is correct but inefficient.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   LCS-based DP is classic for minimal delete operations [OK]

Hint: Minimal deletes -> LCS-based DP [OK]

Common Mistakes:

• Thinking greedy deletion works optimally
• Ignoring subsequence order
• Confusing sorting with subsequence

2. Given the following code for computing edit distance, what is the value of dp[3] after the inner loop finishes when word1 = 'abc' and word2 = 'ac' during the second iteration of the outer loop (i=2)?

easy

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Trace dp array initialization and first iteration

   Initially dp = [0,1,2]. After i=1 (word1[0]='a'), dp updates to [1,0,1].

2. Step 2: Trace second iteration i=2 (word1[1]='b')

   Start dp[0]=2. For j=1 (word2[0]='a'), chars differ, dp[1]=min(0+1,2+1,1+1)=1. For j=2 (word2[1]='c'), chars differ, dp[2]=min(1+1,1+1,0+1)=1. So dp after inner loop: [2,1,1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual step-by-step matches dp[3]=2 [OK]

Hint: Track dp updates carefully for each i,j iteration [OK]

Common Mistakes:

• Off-by-one indexing
• Confusing prev and temp variables
• Mis-updating dp[0]

3. What is the time and space complexity of the space-optimized bottom-up DP solution for the longest palindromic subsequence problem on a string of length n?

medium

A. Time: O(n^2), Space: O(n)

B. Time: O(n), Space: O(n^2)

C. Time: O(n^3), Space: O(n)

D. Time: O(n^2), Space: O(n^2)

Solution

1. Step 1: Identify nested loops over indices i and j

   Outer loop runs n times, inner loop up to n times -> O(n^2) time.

2. Step 2: Analyze space usage

   Space optimized DP uses a single 1D array of size n -> O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time quadratic due to substring pairs, space linear due to optimization [OK]

Hint: Nested loops -> O(n²) time; single array -> O(n) space [OK]

Common Mistakes:

• Confusing recursion stack space
• Assuming O(n^3) due to nested loops
• Forgetting space optimization

4. Suppose you want to compute the edit distance where characters can be replaced multiple times (reuse allowed) and the cost of replacement depends on character pairs. Which modification to the classic DP approach correctly handles this variant?

hard

A. Use bottom-up DP with a cost matrix for replacements and update dp accordingly

B. Modify DP to allow revisiting states multiple times with memoization

C. Switch to a greedy approach that picks cheapest replacement at each mismatch

D. Use the same DP but add a third dimension for replacement cost per character pair

Solution

1. Step 1: Understand replacement cost depends on character pairs

   Replacement cost varies, so DP must incorporate a cost matrix for each character pair.

2. Step 2: Adapt bottom-up DP to use cost matrix in dp updates

   When characters differ, dp[j] updates using the specific replacement cost from the matrix, ensuring correct minimal cost.

3. Step 3: Confirm approach handles reuse and varying costs

   Bottom-up DP with cost matrix correctly accumulates minimal costs allowing multiple replacements.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP with cost matrix handles variable replacement costs [OK]

Hint: Incorporate cost matrix into DP transitions for variable replacements [OK]

Common Mistakes:

• Adding extra DP dimension unnecessarily
• Using memoization without cost matrix
• Trying greedy which fails globally

5. Suppose the regular expression pattern is extended to allow '+' which matches one or more of the preceding element (in addition to '.' and '*'). Which modification to the DP approach correctly handles '+' without increasing time complexity beyond O(m*n)?

hard

A. Modify dp update to require at least one match before repeating for '+', i.e., dp[j] = (prev and match) or (dp[j] and match) but not dp[j - 2] alone, and initialize accordingly

B. Add a separate DP state dimension to track '+' matches explicitly

C. Treat '+' exactly like '*' by copying dp[j] = dp[j] or dp[j - 2] logic

D. Replace '+' with equivalent '.*' in pattern preprocessing

Solution

1. Step 1: Understand '+' semantics

   '+' requires at least one occurrence of preceding element, unlike '*' which allows zero occurrences.

2. Step 2: Adjust DP update logic

   For '+', dp[j] must be true if previous character matched (prev and match) or if repeating the match (dp[j] and match), but not from dp[j - 2] alone which allows zero occurrences.

3. Step 3: Confirm time complexity

   This modification keeps DP table size and iteration unchanged, preserving O(m*n) time complexity.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   '+' requires at least one match, so zero occurrence logic must be excluded [OK]

Hint: '+' differs from '*' by disallowing zero occurrences [OK]

Common Mistakes:

• Treating '+' exactly like '*' allowing zero occurrences