97. Interleaving String

At a Glance

Topic: dp-2d
Pattern: Dynamic Programming (two-string matching with merge order)
Difficulty: Medium
Companies: Google, Amazon, Apple, Microsoft, Bloomberg
Frequency: High
LeetCode: 97

Problem (one-liner)

Given s1, s2, and s3, determine whether s3 can be formed by interleaving s1 and s2 while preserving each string’s internal character order. Input: three strings. Output: boolean.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

“Interleave” two strings into a third
Length must satisfy len(s3) == len(s1) + len(s2)
At each step take next from s1 or s2 if it matches s3

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — DFS all branches — exponential.
Better — reachable[i][j] whether first i+j of s3 matches first i of s1 and first j of s2 — O(m*n) time / O(m*n) space.
Optimal — 1D rolling on shorter dimension — O(m*n) time / O(min(m,n)) space. <- pick this in interview.

Optimal Solution

Go

package main

func isInterleaveTable(s1 string, s2 string, s3 string) bool {
	length1 := len(s1)
	length2 := len(s2)
	if length1+length2 != len(s3) {
		return false
	}
	reachable := make([][]bool, length1+1)
	for index := range reachable {
		reachable[index] = make([]bool, length2+1)
	}
	reachable[0][0] = true
	for prefix1 := 0; prefix1 <= length1; prefix1++ {
		for prefix2 := 0; prefix2 <= length2; prefix2++ {
			if prefix1 == 0 && prefix2 == 0 {
				continue
			}
			position := prefix1 + prefix2 - 1
			matchFromFirst := false
			if prefix1 > 0 && reachable[prefix1-1][prefix2] && s1[prefix1-1] == s3[position] {
				matchFromFirst = true
			}
			matchFromSecond := false
			if prefix2 > 0 && reachable[prefix1][prefix2-1] && s2[prefix2-1] == s3[position] {
				matchFromSecond = true
			}
			reachable[prefix1][prefix2] = matchFromFirst || matchFromSecond
		}
	}
	return reachable[length1][length2]
}

func isInterleave(s1 string, s2 string, s3 string) bool {
	length1 := len(s1)
	length2 := len(s2)
	if length1+length2 != len(s3) {
		return false
	}
	previous := make([]bool, length2+1)
	current := make([]bool, length2+1)
	previous[0] = true
	for prefix2 := 1; prefix2 <= length2; prefix2++ {
		previous[prefix2] = previous[prefix2-1] && s2[prefix2-1] == s3[prefix2-1]
	}
	for prefix1 := 1; prefix1 <= length1; prefix1++ {
		current[0] = previous[0] && s1[prefix1-1] == s3[prefix1-1]
		for prefix2 := 1; prefix2 <= length2; prefix2++ {
			position := prefix1 + prefix2 - 1
			fromFirst := previous[prefix2] && s1[prefix1-1] == s3[position]
			fromSecond := current[prefix2-1] && s2[prefix2-1] == s3[position]
			current[prefix2] = fromFirst || fromSecond
		}
		copy(previous, current)
	}
	return previous[length2]
}

JavaScript

function isInterleave(s1, s2, s3) {
	const length1 = s1.length;
	const length2 = s2.length;
	if (length1 + length2 !== s3.length) return false;
	const previous = new Array(length2 + 1).fill(false);
	previous[0] = true;
	for (let prefix2 = 1; prefix2 <= length2; prefix2++) {
		previous[prefix2] =
			previous[prefix2 - 1] && s2[prefix2 - 1] === s3[prefix2 - 1];
	}
	for (let prefix1 = 1; prefix1 <= length1; prefix1++) {
		const current = new Array(length2 + 1).fill(false);
		current[0] = previous[0] && s1[prefix1 - 1] === s3[prefix1 - 1];
		for (let prefix2 = 1; prefix2 <= length2; prefix2++) {
			const position = prefix1 + prefix2 - 1;
			const fromFirst =
				previous[prefix2] && s1[prefix1 - 1] === s3[position];
			const fromSecond =
				current[prefix2 - 1] && s2[prefix2 - 1] === s3[position];
			current[prefix2] = fromFirst || fromSecond;
		}
		for (let index = 0; index <= length2; index++) {
			previous[index] = current[index];
		}
	}
	return previous[length2];
}