Interleaving String

Interleaving String

1. What is this problem about?

The Interleaving String interview question asks if a string s3 can be formed by "interleaving" two other strings, s1 and s2. Interleaving means that the relative order of characters from both s1 and s2 is preserved, and every character from both is used exactly once to form s3.

2. Why is this asked in interviews?

Companies like Goldman Sachs, Google, and Amazon use the Interleaving String coding problem to test a candidate's knowledge of Dynamic Programming. While a simple recursion seems intuitive, it leads to an exponential search space. This problem evaluations whether you can identify overlapping subproblems and use memoization or a 2D table to solve it in $O(N \cdot M)$ time.

3. Algorithmic pattern used

This is a classic 2D Dynamic Programming problem.

1. State: dp[i][j] is a boolean indicating if s3[0...i+j-1] can be formed by interleaving s1[0...i-1] and s2[0...j-1].
2. Base Case: dp[0][0] = true (empty strings).
3. Transition:
   • If s1[i-1] == s3[i+j-1], then dp[i][j] = dp[i-1][j].
   • If s2[j-1] == s3[i+j-1], then dp[i][j] = dp[i][j] || dp[i][j-1]. This builds the answer from the ground up by checking if the current character of s3 could have come from either s1 or s2.

4. Example explanation

s1 = "aab", s2 = "db", s3 = "aadbb"

• dp[1][0]: s3[0] is 'a', s1[0] is 'a'. Match! dp[1][0] = true.
• dp[2][0]: s3[1] is 'a', s1[1] is 'a'. Match! dp[2][0] = true.
• dp[2][1]: s3[2] is 'd', s2[0] is 'd'. Match! dp[2][1] = true.
• ... and so on. If any path reaches dp[length1][length2], the answer is true.

5. Common mistakes candidates make

• Greedy Logic: Thinking you can just pick the character from $s1$ if it matches, and $s2$ otherwise. If both match, you must explore both paths, which greedy fails to do.
• Length Mismatch: Forgetting to check if s1.length + s2.length == s3.length at the very beginning.
• Recursive TLE: Writing recursion without a visited or memo table.

6. Interview preparation tip

Practice reducing 2D DP to 1D DP. For this problem, you only need the previous row of the DP table, allowing you to optimize space from $O(N \cdot M)$ to $O(\min(N, M))$. This is a high-level String interview pattern skill.