How do you solve Interleaving String?

Use top-down memoized recursion (DP) with a helper function dp(i, j) that returns true if s3[:i+j] is an interleaving of s1[:i] and s2[:j]. The function checks base cases, memoizes results to avoid recomputation, and explores both possibilities of taking the next character from s1 or s2 if they match s3. This approach runs in O(n*m) time and space, where n and m are lengths of s1 and s2.

Interleaving String

Q: What is the time complexity of Interleaving String?

O(n * m). Each state (i, j) is computed once and stored in memo. There are at most n * m states, where n and m are lengths of s1 and s2.

Q: What pattern does Interleaving String use?

The Pattern: Dynamic Programming (Top-Down Memoization for Sequence Interleaving) The Heuristic: When verifying if one sequence can be formed by interleaving two others while preserving order, model the problem as a state machine over indices and use memoization to avoid exponential recomputation of overlapping subproblems.

Medium Dynamic Programming

Problem

Given three strings s1, s2, and s3, return true if s3 is formed by an interleaving of s1 and s2, and false otherwise.

0 ≤ s1.length, s2.length ≤ 100
0 ≤ s3.length ≤ 200
s1, s2, and s3 consist of lowercase English letters.

Example

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

Output: true

The string s3 can be formed by interleaving s1 and s2 as follows: take 'a' from s1, then 'a' from s1, then 'd' from s2, then 'b' from s2, then 'b' from s1, then 'c' from s2, then 'b' from s1, then 'c' from s1, then 'a' from s2, then 'c' from s1. This preserves the order of characters in s1 and s2.

Approach

Straightforward Solution

A brute-force approach tries all possible ways to interleave s1 and s2 to form s3, which leads to exponential time complexity due to the combinatorial explosion of choices.

Core Observation

The problem reduces to verifying if s3 can be formed by choosing characters sequentially from s1 and s2 without reordering either string. The key is that the sum of lengths of s1 and s2 must equal the length of s3, and at each step, the next character in s3 must match the next character in either s1 or s2.

Path to Optimal

Preview

Recognizing overlapping subproblems and optimal substructure, the problem can be solved with dynamic programming. Define a state dp(i, j) representing whether s3[:i+j] can be formed by interleaving s1[:i] and s2[:j]…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use top-down memoized recursion (DP) with a helper function dp(i, j) that returns true if s3[:i+j] is an interleaving of s1[:i] and s2[:j]…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n * m)

Each state (i, j) is computed once and stored in memo. There are at most n * m states, where n and m are lengths of s1 and s2.

Space

O(n * m)

The memo dictionary stores results for each state (i, j), requiring O(n * m) auxiliary space. The recursion stack depth is at most n + m, which is bounded by O(n + m).

Pattern Spotlight

Dynamic Programming (Top-Down Memoization for Sequence Interleaving)

When verifying if one sequence can be formed by interleaving two others while preserving order, model the problem as a state machine over indices and use memoization to avoid exponential recomputation of overlapping subproblems.

Solution

Python

1class Solution:
  def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
      if len(s1) + len(s2) != len(s3):
          return False
      
      memo = {}
7
      def dp(i, j):
          if i == len(s1) and j == len(s2):
              return True
          if (i, j) in memo:
              return memo[(i, j)]
          
          k = i + j
          res = False
          if i < len(s1) and s1[i] == s3[k]:
              res = dp(i + 1, j)
          
          if not res and j < len(s2) and s2[j] == s3[k]:
              res = dp(i, j + 1)
          
          memo[(i, j)] = res
          return res
24
      return dp(0, 0)

Step-by-Step Solution

Validate Lengths and Initialize Memoization Cache

3if len(s1) + len(s2) != len(s3):
4    return False
6memo = {}

Objective

To quickly rule out impossible cases by comparing lengths and prepare a cache to store intermediate results.

Key Insight

If the combined lengths of s1 and s2 do not equal s3's length, s3 cannot be an interleaving, allowing an immediate return of false. Initializing a memo dictionary enables caching of subproblem results, which is essential to avoid redundant recursive calls and exponential blowup.

Interview Quick-Check

Core Logic

Checking length equality is a necessary precondition for interleaving; failing this check immediately prunes impossible inputs.

Common Pitfalls & Bugs

Forgetting this length check leads to unnecessary computation and incorrect results on invalid inputs.

State & Boundaries

Memoization cache keys are tuples (i, j) representing indices in s1 and s2, ensuring unique states.

Recursively Explore Interleaving Possibilities with Memoization

To determine if s3 can be formed by interleaving s1 and s2 starting from indices i and j, using memoization to avoid repeated work.

Return Final Interleaving Result from Initial State

To start the recursive exploration from the beginning of both strings and return the final boolean result.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 11 Critical

if (i, j) in memo:

Check if the current state (i, j) has been computed before.

Memoization lookup prevents redundant recursive calls, drastically reducing time complexity.

Line 3 Critical

if len(s1) + len(s2) != len(s3):

Check if combined lengths of s1 and s2 equal length of s3.

This is a fundamental feasibility check; if lengths don't match, s3 cannot be an interleaving, allowing immediate termination.

Line 9 Critical

if i == len(s1) and j == len(s2):

Check if both s1 and s2 have been fully consumed.

Reaching the end of both strings means a successful interleaving has been found, serving as the base case for recursion.

Full line-by-line criticality + rationale for all 17 lines available on Pro.

Test Your Understanding

Why is memoization critical in this recursive solution for interleaving strings?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Interleaving String from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Interleaving String drill

or drill a free problem

1	`class Solution:`
2	`def isInterleave(self, s1: str, s2: str, s3: str) -> bool:`
3	`if len(s1) + len(s2) != len(s3):`
4	`return False`
5
6	`memo = {}`
7
8	`def dp(i, j):`
9	`if i == len(s1) and j == len(s2):`
10	`return True`
11	`if (i, j) in memo:`
12	`return memo[(i, j)]`
13
14	`k = i + j`
15	`res = False`
16	`if i < len(s1) and s1[i] == s3[k]:`
17	`res = dp(i + 1, j)`
18
19	`if not res and j < len(s2) and s2[j] == s3[k]:`
20	`res = dp(i, j + 1)`
21
22	`memo[(i, j)] = res`
23	`return res`
24
25	`return dp(0, 0)`