Interleaving String - Video Solutions

Problem Overview: You are given three strings s1, s2, and s3. The goal is to determine whether s3 can be formed by interleaving characters from s1 and s2 while preserving the original order of characters in both strings.

The key constraint is order preservation. You can switch between the two strings at any time, but characters from each string must appear in the same relative order. This naturally leads to exploring combinations of prefixes from both strings.

Approach 1: Recursive with Memoization (Top-Down DP) (Time: O(m*n), Space: O(m*n))

Think of the problem as building s3 character by character while choosing whether the next character comes from s1 or s2. Use recursion with two indices i and j representing how many characters have been consumed from s1 and s2. The next character in s3 is at position i + j. If s1[i] matches s3[i+j], recursively move to (i+1, j). If s2[j] matches, move to (i, j+1).

Without caching, the recursion explores the same states many times. Memoization stores results for each state (i, j), avoiding recomputation. This reduces the exponential search space to a grid of size m × n. This approach is intuitive because it directly models the decision process and works well when explaining the logic during interviews involving dynamic programming and recursion.

Approach 2: Dynamic Programming (Bottom-Up) (Time: O(m*n), Space: O(m*n))

The bottom-up DP solution builds a table dp[i][j] where each cell indicates whether the first i characters of s1 and the first j characters of s2 can form the prefix s3[0..i+j-1]. Initialize dp[0][0] as true since empty strings form an empty interleaving.

Fill the table by iterating over all i and j. If the current character of s1 matches s3, propagate the value from dp[i-1][j]. If the character from s2 matches, propagate from dp[i][j-1]. Each state checks whether either path leads to a valid interleaving.

This transforms the problem into a grid traversal where each cell depends on the top and left neighbors. The approach is deterministic, avoids recursion overhead, and is typically preferred for production code involving string processing and DP state transitions.

Recommended for interviews: Interviewers usually expect the dynamic programming formulation with a dp[i][j] state. Starting with the recursive idea demonstrates understanding of the decision tree, and then optimizing it with memoization or converting it to bottom-up DP shows strong problem-solving skills. The bottom-up DP approach is the cleanest final solution with predictable O(m*n) time and space complexity.