Domain 2MediumCORE

Interleaving String

We are given three strings s1, s2, and s3. The goal is to determine if s3 can be constructed as an interleaving of characters from s1 and s2. Crucially, the relative order of characters within each source string must remain unchanged.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#String#Dynamic Programming

97. Interleaving String

Model: qwen3.5:9b
Topics: String,Dynamic Programming
FAANG asked: 1
Acceptance rate: 32.8%


Problem Breakdown

We are given three strings s1, s2, and s3. The goal is to determine if s3 can be constructed as an interleaving of characters from s1 and s2. Crucially, the relative order of characters within each source string must remain unchanged.

Key Constraints & Edge Cases:

  • Length Mismatch: If len(s1) + len(s2) does not equal len(s3), it is impossible to form s3 regardless of content. We should check this immediately for an O(1)O(1) optimization.
  • Empty Strings: The problem allows empty inputs (e.g., Example 3). If both source strings are empty, the target must also be empty to return True. Our DP logic naturally handles these if initialized correctly (dp[0][0] = True).
  • Characters: Lowercase English letters only; no overflow or negative number concerns.

Intuition

A brute-force approach would try every possible permutation of picking characters from s1 and s2, which leads to exponential time complexity O(2N+M)O(2^{N+M}). This is inefficient because we revisit the same states repeatedly (e.g., reaching a specific index in s3 via different paths).

This suggests Dynamic Programming. We can define a state based on how many characters from each source string have been consumed. Let’s say dp[i][j] represents whether it’s possible to form the prefix of length i + j in s3 using the first i characters of s1 and the first j characters of s2.

The transition logic is straightforward: To reach state (i, j), we could have come from either:

  1. State (i-1, j) (we just consumed a character from s1). This requires matching s3[i+j-1] with s1[i-1].
  2. State (i, j-1) (we just consumed a character from s2). This requires matching s3[i+j-1] with s2[j-1].

If either path is valid and the characters match, then state (i, j) is True.

Approach

We will use a 2D boolean table of size (len(s1) + 1) x (len(s2) + 1).

  1. Initialization: Create dp array filled with False. Set dp[0][0] = True because empty strings can form an empty string.
  2. Base Cases for Rows/Cols: Fill the first row (s1 exhausted, only using s2) and first column (s2 exhausted, only using s1). This checks if prefixes of s3 match exactly with one source string alone.
  3. Iteration: Iterate through all valid indices (i, j). For each cell:
    • Check validity from top (using s1) AND check character equality.
    • OR check validity from left (using s2) AND check character equality.
  4. Result: Return the value at dp[len(s1)][len(s2)].

Note on Follow-up: While we use O(M×N)O(M \times N) space here for clarity, this can be optimized to O(min⁡(N,M))O(\min(N, M)) by observing that row i only depends on row i-1, allowing us to reduce the table to a 1D array.

Complexity Analysis

  • Time: O(M×N)O(M \times N) where M=len(s1)M = len(s1) and N=len(s2)N = len(s2). We visit each cell in our DP table exactly once, performing constant work per cell.
  • Space: O(M×N)O(M \times N) for the 2D boolean array.
    • Follow-up Optimization: To satisfy the follow-up constraint of using only O(len(s2)) space (or linear with respect to one string), we can reduce this table to a single row, updating values in place while keeping track of diagonal dependencies or swapping rows.

Solution

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # Optimization 1: Length check (O(1))
        if len(s1) + len(s2) != len(s3):
            return False
        
        m, n = len(s1), len(s2)
        
        # dp[i][j] means s3[:i+j] can be formed by interleaving 
        # s1[:i] and s2[:j]. We use a 2D array for clarity.
        # To satisfy the follow-up O(N) space, we could reduce this to 1 row.
        dp = [[False] * (n + 1) for _ in range(m + 1)]

        # Base case: empty strings form an empty string
        dp[0][0] = True
        
        # Initialize first column (only s2 used, s1 exhausted)
        for j in range(1, n + 1):
            if s3[j - 1] == s2[j - 1]:
                dp[0][j] = dp[0][j-1]
        
        # Initialize first row (only s1 used, s2 exhausted)
        for i in range(1, m + 1):
            if s3[i - 1] == s1[i - 1]:
                dp[i][0] = dp[i-1][0]

        # Fill the DP table
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                index_s3 = i + j - 1
                
                # Check if we can transition from s2 (left neighbor)
                match_from_s2 = dp[i][j-1] and s3[index_s3] == s2[j-1]
                
                # Check if we can transition from s1 (top neighbor)
                match_from_s1 = dp[i-1][j] and s3[index_s3] == s1[i-1]
                
                dp[i][j] = match_from_s2 or match_from_s1
                
        return dp[m][n]

# Example usage:
sol = Solution()
print(sol.isInterleave("aabcc", "dbbca", "aadbbcbcac")) # True

Edge Cases Handled

  • Length Mismatch: The initial check len(s1) + len(s2) != len(s3) returns False immediately, preventing index errors and saving time.
  • Empty Inputs:
    • If s1 is empty but s2 matches s3, the first column initialization handles this correctly (dp[0][j]).
    • If both are empty, loops don’t run or return True based on base case logic.
  • Partial Matches: The DP table ensures we only proceed if a character match exists from either source string at that specific step.