What is the brute force approach and complexity for Interleaving String?

Recurse on (i, j): the last letter placed came from s1 or from s2, so try both with time complexity O(2^(N + M)) and space complexity O(N + M).

What is the optimal approach and complexity for Interleaving String?

Keep one row over s2 and update it for each letter of s1; O(M) extra space with optimal time complexity O(N · M) and space complexity O(M).

How do you identify the pattern for Interleaving String?

Look for key signals in the prompt: "interleaving" indicates Two sequences are merged in order. Each letter of s3 comes from s1 or s2, and the order inside each string is kept.; "s3 is formed from s1 and s2" indicates The lengths must add up, and the letters of s3 are placed one at a time, so the state is a pair (i, j).; "is it possible (true or false)" indicates A boolean table. Each cell is true or false, not a cost, so there is no minimum to choose..

Interleaving String

Medium·LeetCode #97 Pro OnlySlight Variation

LeetCode

Problem Statement

You get three strings, s1, s2 and s3. Decide whether s3 can be made by interleaving s1 and s2.

An interleaving takes letters from s1 and s2, one at a time, so that every letter of s3 comes from exactly one of them. The letters of s1 must appear in their original order, and so must the letters of s2.

Input

Three strings s1, s2 and s3.

Output

true if s3 is an interleaving of s1 and s2, otherwise false.

Example 1

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

Output: true

Cut s1 into aa, bc, c and s2 into dbbc, a. Then alternate the pieces: aa + dbbc + bc + a + c = aadbbcbcac.

Example 2

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

Output: false

The a at position 6 of s3 must come from s2. But s2 has a c before its a, and s3 has no c before position 6.

Example 3

Input: s1 = "", s2 = "", s3 = ""

Output: true

Both strings are empty, so the empty string is the only interleaving.

Constraints

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

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“interleaving”

→ Two sequences are merged in order. Each letter of s3 comes from s1 or s2, and the order inside each string is kept.

“s3 is formed from s1 and s2”

→ The lengths must add up, and the letters of s3 are placed one at a time, so the state is a pair (i, j).

“is it possible (true or false)”

→ A boolean table. Each cell is true or false, not a cost, so there is no minimum to choose.

Approach Complexity Ladder

Brute Force — the last letter placed came from s1 or from s2O(2^(N + M))O(N + M)

Recurse on (i, j): the last letter placed came from s1 or from s2, so try both

Better — 2D table dp[i][j], one cell per pair of prefixesO(N · M)O(N · M)

dp[i][j] = can the first i letters of s1 and the first j letters of s2 make the first i + j letters of s3

Optimal — one row, updated in placeO(N · M)O(M)

Keep one row over s2 and update it for each letter of s1; O(M) extra space

Brute Force Intuition

Let can(i, j) say whether the first i letters of s1 and the first j letters of s2 can make the first i + j letters of s3. The last letter placed is s3[i + j − 1]. It came from s1 when s1[i − 1] equals it and can(i − 1, j) is true. It came from s2 when s2[j − 1] equals it and can(i, j − 1) is true. The answer is can for the full lengths, after the length check.

Recognition rule for this sub-pattern:

Each cell picks the cheapest of insert / delete / replace (or the pattern rule for *, ?, .).

Remember this · DP — Strings

Trigger

Longest common subsequence, edit distance, palindromes, matching with wildcards, interleaving.

Think

Look at the last characters: if they match, what do I do? If not, what are my options?

Key question

What does dp[i][j] mean, and what are the empty-string base cases?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Strings translate into production architectures and low-level memory mechanics.

LLD Architecture