Interleaving String - Video Solutions

Problem Overview: You receive three strings s1, s2, and s3. The task is to determine whether s3 can be formed by interleaving characters from s1 and s2 while preserving the relative order of characters from each string. Characters from both strings can be mixed, but their internal order cannot change.

Approach 1: Pure Recursion (Exponential Time)

The straightforward idea is to try building s3 from left to right. At position k in s3, check whether the character matches the next character in s1 or s2. If both match, branch into two recursive calls. If only one matches, continue with that branch. This approach explores every possible interleaving combination, which leads to O(2^(m+n)) time complexity and O(m+n) recursion stack space. It works conceptually but quickly becomes impractical for larger inputs due to repeated subproblems.

Approach 2: Recursive with Memoization (O(m*n) time, O(m*n) space)

The recursive solution repeatedly checks the same states: positions i in s1 and j in s2. These positions uniquely determine the index k = i + j in s3. Store results of these states in a memo table so each pair (i, j) is computed once. When recursion revisits the same state, return the cached result instead of recomputing. This converts the exponential search into a polynomial solution with O(m*n) time and O(m*n) memory. The method clearly expresses the branching logic while eliminating duplicate work. It fits naturally with problems involving overlapping subproblems in dynamic programming.

Approach 3: Bottom-Up Dynamic Programming (O(m*n) time, O(m*n) space)

The iterative DP version builds a table dp[i][j] representing whether the first i characters of s1 and the first j characters of s2 can form the first i + j characters of s3. Initialize dp[0][0] = true. For each cell, check whether the current character in s3 matches the next character in either string and whether the previous state was valid. The transition becomes:

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])

This approach systematically fills the grid and avoids recursion overhead. Time complexity is O(m*n) and space complexity is also O(m*n). With a small optimization, the DP table can be compressed to a single row for O(n) space. This method highlights how string problems often reduce to grid-style DP similar to edit distance.

Recommended for interviews: The bottom-up dynamic programming approach is what most interviewers expect. Start by explaining the recursive idea to demonstrate understanding of the interleaving decision at each step. Then convert the repeated states into memoization or tabulation to reach the optimal O(m*n) solution. Showing this progression demonstrates strong problem-solving and mastery of dynamic programming patterns.