115. Distinct Subsequences

At a Glance

• Topic: dp-2d
• Pattern: Dynamic Programming — two-sequence (count ways to match subsequence)
• Difficulty: Hard
• Companies: Google, Amazon, Meta, Uber, Airbnb
• Frequency: Medium
• LeetCode: 115

Problem (one-liner)

Given strings source and target, return the number of distinct non-empty subsequences of source that equal target (modulo large prime 1e9+7 on LeetCode).

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

• Count subsequences equal to target — not yes/no
• Two strings → 2D DP; recurrence resembles “delete from source” or match progression through target
• Overlapping structure → table, not raw recursion

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.

Approaches

• Backtrack enumerate all subsequences — O(2^len(source)) — impossible.
• DP ways[sourceIndex][targetIndex] — number of ways using prefix of source to form prefix of target — O(|source| * |target|) time, O(|target|) space with rolling row — optimal.

Optimal Solution

Go

func numDistinct(source string, target string) int {
	const modulus = 1_000_000_007
	sourceLen := len(source)
	targetLen := len(target)
	// ways[j] = ways to form target[0:j) using processed prefix of source
	ways := make([]int, targetLen+1)
	ways[0] = 1
	for sourceIndex := 0; sourceIndex < sourceLen; sourceIndex++ {
		// iterate target backwards so each char of source used at most once per path
		for targetIndex := targetLen; targetIndex >= 1; targetIndex-- {
			if source[sourceIndex] == target[targetIndex-1] {
				ways[targetIndex] = (ways[targetIndex] + ways[targetIndex-1]) % modulus
			}
		}
	}
	return ways[targetLen]
}

JavaScript

function numDistinct(source, target) {
  const modulus = 1_000_000_007;
  const sourceLen = source.length;
  const targetLen = target.length;
  const ways = new Array(targetLen + 1).fill(0);
  ways[0] = 1;
  for (let sourceIndex = 0; sourceIndex < sourceLen; sourceIndex += 1) {
    for (let targetIndex = targetLen; targetIndex >= 1; targetIndex -= 1) {
      if (source[sourceIndex] === target[targetIndex - 1]) {
        ways[targetIndex] = (ways[targetIndex] + ways[targetIndex - 1]) % modulus;
      }
    }
  }
  return ways[targetLen];
}

Walkthrough

source = "rabbbit", target = "rabbit". When source char matches target tail, add ways that matched one shorter prefix.

Invariant: After processing source[0:sourceIndex+1), ways[j] counts distinct alignments of target[0:j).

Edge Cases

• target empty — usually 1 (empty subsequence) per problem definition; LeetCode uses non-empty target in constraints
• target longer than source — 0
• All characters identical — combinatorial blow-up handled by DP count

Pitfalls

• Forward inner loop over target — double-counts using same source char multiple times in one path; reverse inner loop fixes one-pass row update
• Integer overflow — apply modulus each addition
• Confusing subsequence vs substring

Similar Problems

• 1143. Longest Common Subsequence — 2D alignment family (Medium)
• 72. Edit Distance — edit cost variant (Hard)
• 10. Regular Expression Matching — pattern matching DP (Hard)

Variants

• No modulus / return bigint — same recurrence, wider integer type
• Print all distinct subsequences — backtrack with pruning (exponential output)
• Multiple targets — tensor DP or automaton merge

Mind-Map Tags

#two-string-dp #subsequence-count #rolling-array #modulo #reverse-inner-loop