What is the brute force approach and complexity for Distinct Subsequences?

Recurse on (i, j): skip s's last letter, or if it matches, use it for t's last letter with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Distinct Subsequences?

One array row[j]; for each letter of s, update j from high to low with optimal time complexity O(N · M) and space complexity O(M).

How do you identify the pattern for Distinct Subsequences?

Look for key signals in the prompt: "number of distinct subsequences" indicates We count ways, not the best length, so each cell adds counts instead of taking a max.; "equals t" indicates Two strings, one table over prefixes of s and t, the same shape as LCS.; "the answer fits in 32 bits" indicates The answer is small, but middle counts may not be. Use a wider unsigned type..

Distinct Subsequences

Hard·LeetCode #115 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

You are given two strings s and t. Count the ways to get t by deleting some letters from s. Two ways are different when they keep a different set of positions in s, even if they spell the same text. Return the count. The test cases make sure the answer fits in a 32-bit signed integer.

Input

Two strings, s and t. The letters are English letters, upper or lower case.

Output

The number of ways t can be made by deleting letters from s.

Example 1

Input: s = "rabbbit", t = "rabbit"

Output: 3

s has three b's, and rabbit needs two of them. Choosing which two b's gives 3 ways.

Example 2

Input: s = "babgbag", t = "bag"

Output: 5

Five different sets of positions in s spell bag.

Constraints

• 1 ≤ s.length, t.length ≤ 1000
• The answer fits in a 32-bit signed integer.

Pattern Recognition Clues

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

“number of distinct subsequences”

→ We count ways, not the best length, so each cell adds counts instead of taking a max.

“equals t”

→ Two strings, one table over prefixes of s and t, the same shape as LCS.

“the answer fits in 32 bits”

→ The answer is small, but middle counts may not be. Use a wider unsigned type.

Approach Complexity Ladder

Brute Force — recursion: skip the letter, or use itO(2^N)O(N)

Recurse on (i, j): skip s's last letter, or if it matches, use it for t's last letter

Better — a full table of waysO(N · M)O(N · M)

dp[i][j] for every pair of prefixes; each cell is filled once from two cells above

Optimal — one row, letters of t from high to lowO(N · M)O(M)

One array row[j]; for each letter of s, update j from high to low

Brute Force Intuition

Let ways(i, j) be the number of ways the first j letters of t appear among the first i letters of s. If j = 0, there is exactly one way: use nothing. If i = 0 and j > 0, there are none. Otherwise skip s[i−1], which gives ways(i−1, j). If s[i−1] = t[j−1], also use it, which gives ways(i−1, j−1). Add the two cases.

Recognition rule for this sub-pattern:

Match → 1 + dp[i−1][j−1]; otherwise max(dp[i−1][j], dp[i][j−1]). Counting versions add the cases instead of taking a max.

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