What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 12 patterns and 187 archetypes is 100% free to access with no credit card required. Students receive 40 free compute coins upon registration, +20 daily login coins, and +25 referral coins. A 24-hour unlimited AI coaching pass costs only 5 coins. Alternatively, developers can use Bring-Your-Own-Key (BYOK) for completely free unlimited AI coaching with personal Gemini or OpenAI keys. There are no recurring subscription fees.

What is the refund and cancellation policy?

Hi👋SpeedAlgo has zero recurring subscriptions, zero automatic renewals, and zero hidden billing traps. Because the core platform and learning materials are free, students never face unwanted credit card charges or recurring payment obligations.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo enforces deliberate practice: proving invariants, articulating Big-O tradeoffs, managing edge cases, and defending algorithmic approaches to a Senior SWE AI Mock Coach in an integrated Monaco code editor.

13. Subsequence Counting DP: Distinct Subsequences (LC 115) • Invariant Proof & Speed-Run

Theory Context•Dynamic Programming

HardLC 115

Distinct Subsequences (LeetCode 115)

You will see how one count per prefix of t, updated once per character of s, counts every way t sits inside s.

Target Frequency:GoogleAmazonMicrosoft

You get two strings, s and t. Choose some positions of s and read their letters from left to right, skipping the others: the result is a subsequence of s.

Count how many different choices of positions spell exactly t. Two choices are different when at least one position differs, even though both spell t. Upper-case and lower-case letters are different letters. The answer is never larger than 2^31 - 1.

Worked Examples

Example 1

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

Output:3

Explanation: `s` has three `b`s in a row and `t` needs two of them; every other letter of `t` has exactly one place it can come from. Two of three `b`s can be chosen in 3 ways.

Example 2

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

Output:5

Explanation: Counting positions from 0, the `b`, `a`, `g` can come from positions (0, 1, 3), (0, 1, 6), (0, 5, 6), (2, 5, 6) or (4, 5, 6): 5 choices.

⚖️Formal Constraints & Bounds

1 <= s.length, t.length <= 1000
s and t consist of English letters.

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

A character of s is either skipped or used as the next letter of some prefix of t, so one count per prefix, ways[j], is all the history you need: a matching character adds the count one letter shorter, ways[j - 1], read before that same character changed it.

Real-World Scenario & Production Applications

Scoring how strongly a short pattern occurs inside a long sequence, for example a motif in a DNA read or a keystroke pattern in an event log, often means counting every way the pattern can be picked out in order, gaps allowed. The count comes from the same running tallies, one per prefix of the pattern, updated once per symbol.

Step-by-Step Execution Trace Table

Example 1, s = "rabbbit", t = "rabbit" (n = 6). Each row reads one character ch; only the j with t[j - 1] == ch change, in the order the backwards loop visits them:

Step	`ch`	Updates (`j` from 6 down to 1)	`ways` after the row
Start		`ways = [1] + [0] * 6`	`[1, 0, 0, 0, 0, 0, 0]`
1	`r`	`ways[1] += ways[0]`: 0 + 1 = 1	`[1, 1, 0, 0, 0, 0, 0]`
2	`a`	`ways[2] += ways[1]`: 0 + 1 = 1	`[1, 1, 1, 0, 0, 0, 0]`
3	`b`	`ways[4] += ways[3]`: 0 + 0 = 0, then `ways[3] += ways[2]`: 0 + 1 = 1	`[1, 1, 1, 1, 0, 0, 0]`
4	`b`	`ways[4] += ways[3]`: 0 + 1 = 1, then `ways[3] += ways[2]`: 1 + 1 = 2	`[1, 1, 1, 2, 1, 0, 0]`
5	`b`	`ways[4] += ways[3]`: 1 + 2 = 3, then `ways[3] += ways[2]`: 2 + 1 = 3	`[1, 1, 1, 3, 3, 0, 0]`
6	`i`	`ways[5] += ways[4]`: 0 + 3 = 3	`[1, 1, 1, 3, 3, 3, 0]`
7	`t`	`ways[6] += ways[5]`: 0 + 3 = 3	`[1, 1, 1, 3, 3, 3, 3]`
End		`return ways[6]`	3

Scroll horizontally to see all columns, or expand to full screen

At step 3, ways[4] reads ways[3] = 0 before this b raises it: no "rab" ends before the first b. Running j upwards would raise ways[3] to 1 first and then count "rabb" with one b used twice; carried on, that returns 6.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Read `s` once; `ways[j]` counts the ways to spell `t[:j]` from the characters read so far, and `ways[0] = 1` because the empty prefix is spelled by picking nothing.
2	A character `ch` is either skipped (every count stays) or used as `t[j - 1]` where the letters match: `ways[j] += ways[j - 1]`.
3	The shape: one list of counts for the prefixes of `t`, an outer loop over the characters of `s`, an inner loop over the prefix lengths `j`, one update where the letters match, and the count for the whole of `t` at the end.
4	The trap: `j` runs from `n` down to `1`. Going up, `ways[j - 1]` already includes this `ch`, so one letter fills two places of `t` (`"rabbbit"`, `"rabbit"` gives 6 instead of 3).

Target: Distinct Subsequences (LeetCode 115). `ways[j]` counts the ways to spell `t[:j]` from the letters of `s` read so far. The empty prefix is spelled once, by picking nothing, so `ways[0] = 1`.

Boundary Model: Topologically Ordered Subproblem Recurrence (DAG(Directed Acyclic Graph))

Optimal substructure: DP state dp[i] depends strictly on already-computed subproblems. Rolling array reduces space from O(S) to O(1 tier).

Loop Invariant Termination

Iterate base cases -> compute states in topological transition order (dp[i] = min/max/sum of transitions).

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

Counting how many ways t sits inside s as a subsequence looks like a search over every set of positions, and there are exponentially many. Subsequence Counting DP reads s once instead. After each character it keeps one number per prefix of t: ways[j], the ways to spell t[:j] with the characters read so far. A new character ch either is skipped, which leaves every count as it was, or finishes a prefix whose last letter is ch, which adds the ways to spell the prefix one letter shorter.

🧵 The Analogy: Threading Beads in Order

Think of t as a pattern of beads to thread, and s as a box of beads that come out one at a time. For every partly threaded pattern you keep a tally of how many different ways you got there. When a bead comes out, every tally whose next bead has that colour can grow by one bead, and every tally can also ignore it. You never need to remember which beads were used, only the tallies.

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

ways = [1] + [0] * n
for ch in s:
    for j in range(n, 0, -1):
        if t[j - 1] == ch:
            ways[j] += ways[j - 1]
return ways[n]

This is the two-row recurrence ways[i][j] = ways[i - 1][j] + ways[i - 1][j - 1] (the second term only when s[i - 1] == t[j - 1]) folded into one row. The right-hand side must still be the previous row, so j runs from n down to 1: ways[j - 1] is then read before this ch changes it. Going up, the same letter of s would fill t[j - 2] and t[j - 1] at once.

💡 Summary

Keep ways[j] for every prefix of t, start with ways[0] = 1, and for each character of s add ways[j - 1] into ways[j] where the letters match, walking j backwards. $O(M \cdot N)$ time and $O(N)$ space.

Running j forwards: for j in range(n, 0, -1) runs from n down. Going up, ways[j - 1] already includes the current ch, so one letter of s fills two places of t: "rabbbit", "rabbit" returns 6 instead of 3.
Replacing instead of adding: ways[j] += ways[j - 1], not =. The ways that skip ch are still valid, so "ccc", "c" needs 3, not 1.
No seed for the empty prefix: start with ways = [1] + [0] * n. The empty prefix t[:0] is spelled once, by picking nothing; with ways[0] = 0 no match can ever start.
Reading the wrong letter of t: ways[j] is the count for the prefix t[:j], whose last letter is t[j - 1]. Comparing t[j] == ch matches the next letter instead, and at j = n it runs past the end of t.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots a count of in-order picks and answers it with one running count per prefix of t.

Pattern Recognition Signals

The 10-second spot

"Choose some positions of s and read their letters from left to right" plus "count how many different choices of positions spell exactly t": the order is fixed and every character of s is either picked or skipped, so the question is a count over in-order picks, not one best alignment. That is the signal for Subsequence Counting DP: one running count per prefix of t, updated once per character of s.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

After each character ch of s is read, ways[j] is the number of ways to spell t[:j] with the characters read so far, and ways[0] = 1. For j from n down to 1: if t[j - 1] == ch, then ways[j] += ways[j - 1] (the old ways[j] skip ch, the ways[j - 1] ways finish t[:j] with it). The answer is ways[n].

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

for j in range(n, 0, -1), never upwards: going up, ways[j - 1] already includes the current ch, so one letter fills two places of t and "rabbbit", "rabbit" returns 6 instead of 3.
ways[j] += ways[j - 1], not =: the ways that skip ch stay valid, and "ccc", "c" needs 3, not 1.
ways = [1] + [0] * n: the empty prefix is spelled once, by picking nothing; starting ways[0] at 0 makes every count 0.
Don't recurse on (position in s, position in t) without saving results: the same pairs are solved again and again, exponential in the length of s. The running counts solve each pair once.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use Subsequence Counting DP. Every character of s is either skipped or used as the next letter of t, so I keep one count per prefix of t: ways of j is the number of ways to spell the first j letters with what I've read so far. ways of zero is one, the empty prefix. For each character of s, I walk j from n down to one, and where t of j minus one equals that character, I add ways of j minus one into ways of j. The old value counts the ways that skip the character, and the added value counts the ways that finish with it. Walking j backwards is the trap it avoids: going up, ways of j minus one would already include this same character, and one letter of s would fill two places of t. The answer is ways of n. That's O(M times N) time and O(N) space.

So: ways[j] per prefix of t, ways[0] = 1; for each ch of s, walk j from n down and add ways[j - 1] where t[j - 1] == ch.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(M * N)

Look at the code: for ch in s runs M times, and for each character for j in range(n, 0, -1) runs N times. The body does one comparison, t[j - 1] == ch, and at most one addition, so it is O(1). Building ways takes N + 1 steps once. Total: O(M * N).

SPACE COMPLEXITY

O(N)

The code keeps one list, ways, of N + 1 counts, plus n, ch and j. It never stores a full M x N table: each character's row overwrites the previous one in place, which is safe because j runs backwards. The answer is one integer.

Formal Recurrence Relation

$T(M, N) = O(N) + M \cdot N \cdot O(1) = O(M \cdot N)$

Derivation Progression

Set up the counts

O(N)

ways = [1] + [0] * n builds N + 1 counts once.

Outer loop

M iterations

for ch in s reads every character of s once.

Inner loop

N iterations per character

for j in range(n, 0, -1) visits every prefix length from N down to 1.

Loop body

O(1)

One comparison t[j - 1] == ch and at most one addition ways[j] += ways[j - 1].

Total

O(M * N)

M characters times N prefixes, constant work each; the answer is read from ways[n].

Variable Definitions

$M$

Length of s, the string the letters are picked from

$N$

Length of t, the string to spell (n = len(t) in the code)

Memory Architecture & Bounds

🟣 Call Stack

O(1): iterative, no recursion

🔵 Auxiliary Heap

O(N): the ways list of N + 1 counts

🟢 Output Space

O(1): one integer

Boundary Best / Worst Cases

Best Case

$O(M \cdot N)$ : the inner loop runs over every j even when no letter matches

Average Case

$O(M \cdot N)$

Worst Case

$O(M \cdot N)$

State-Space & Subproblem DAG(Directed Acyclic Graph) Topology

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: **"choose some positions of s and read their letters from left to right"**, **"count how many different choices of positions spell exactly t"**. A count over in-order picks where every character is used or skipped: Subsequence Counting DP, one running count per prefix of t.

CONSTRAINTS & BOUNDS

$M, N \le 1000$ , so $M \cdot N \le 10^6$ cheap steps. Trying every set of positions is $\binom{M}{N}$ , and the memo-free skip-or-use recursion is up to $O(2^M)$ ; the running counts are $O(M \cdot N)$ time and $O(N)$ space. The answer fits a 32-bit integer, but counts for short prefixes of t can be astronomically larger.

FAANG PRODUCTION TRAPS & EDGE CASES

Running j upwards reuses the current character twice ("rabbbit", "rabbit" must return 3, not 6). In C++ or Rust, a count that never reaches the answer can overflow even though the answer fits: use unsigned or wrapping additions there, since every count that does feed ways[n] is never larger than the answer. Python's integers need no change, and the silent wrap-around of Java, Go and C# integers is harmless for the same reason.

Core Algorithmic State Invariants

1. One Count per Prefix of t

After each character of `s`, `ways[j]` is the number of ways to spell `t[:j]` with the characters read so far, and `ways[0] = 1`: the empty prefix is spelled once, by picking nothing.

2. Skip or Use, Read Before Writing

Where `t[j - 1] == ch`, `ways[j] += ways[j - 1]`: the old count skips `ch`, the added count finishes with it. `j` runs from `n` down to `1`, so `ways[j - 1]` is read before this `ch` changes it and one letter never fills two places.

3. One Row, M x N Steps

Each of the M characters walks the N prefixes once with O(1) work, and the counts live in one row that is overwritten in place: O(M * N) time and O(N) space.

Theory Context•Dynamic Programming

HardLC 115

Distinct Subsequences (LeetCode 115)

You will see how one count per prefix of t, updated once per character of s, counts every way t sits inside s.

Target Frequency:GoogleAmazonMicrosoft

You get two strings, s and t. Choose some positions of s and read their letters from left to right, skipping the others: the result is a subsequence of s.

Worked Examples

Example 1

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

Output:3

Explanation: `s` has three `b`s in a row and `t` needs two of them; every other letter of `t` has exactly one place it can come from. Two of three `b`s can be chosen in 3 ways.

Example 2

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

Output:5

Explanation: Counting positions from 0, the `b`, `a`, `g` can come from positions (0, 1, 3), (0, 1, 6), (0, 5, 6), (2, 5, 6) or (4, 5, 6): 5 choices.

⚖️Formal Constraints & Bounds

1 <= s.length, t.length <= 1000
s and t consist of English letters.

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Real-World Scenario & Production Applications

Step-by-Step Execution Trace Table

Example 1, s = "rabbbit", t = "rabbit" (n = 6). Each row reads one character ch; only the j with t[j - 1] == ch change, in the order the backwards loop visits them:

Step	`ch`	Updates (`j` from 6 down to 1)	`ways` after the row
Start		`ways = [1] + [0] * 6`	`[1, 0, 0, 0, 0, 0, 0]`
1	`r`	`ways[1] += ways[0]`: 0 + 1 = 1	`[1, 1, 0, 0, 0, 0, 0]`
2	`a`	`ways[2] += ways[1]`: 0 + 1 = 1	`[1, 1, 1, 0, 0, 0, 0]`
3	`b`	`ways[4] += ways[3]`: 0 + 0 = 0, then `ways[3] += ways[2]`: 0 + 1 = 1	`[1, 1, 1, 1, 0, 0, 0]`
4	`b`	`ways[4] += ways[3]`: 0 + 1 = 1, then `ways[3] += ways[2]`: 1 + 1 = 2	`[1, 1, 1, 2, 1, 0, 0]`
5	`b`	`ways[4] += ways[3]`: 1 + 2 = 3, then `ways[3] += ways[2]`: 2 + 1 = 3	`[1, 1, 1, 3, 3, 0, 0]`
6	`i`	`ways[5] += ways[4]`: 0 + 3 = 3	`[1, 1, 1, 3, 3, 3, 0]`
7	`t`	`ways[6] += ways[5]`: 0 + 3 = 3	`[1, 1, 1, 3, 3, 3, 3]`
End		`return ways[6]`	3

Scroll horizontally to see all columns, or expand to full screen

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Read `s` once; `ways[j]` counts the ways to spell `t[:j]` from the characters read so far, and `ways[0] = 1` because the empty prefix is spelled by picking nothing.
2	A character `ch` is either skipped (every count stays) or used as `t[j - 1]` where the letters match: `ways[j] += ways[j - 1]`.
3	The shape: one list of counts for the prefixes of `t`, an outer loop over the characters of `s`, an inner loop over the prefix lengths `j`, one update where the letters match, and the count for the whole of `t` at the end.
4	The trap: `j` runs from `n` down to `1`. Going up, `ways[j - 1]` already includes this `ch`, so one letter fills two places of `t` (`"rabbbit"`, `"rabbit"` gives 6 instead of 3).

Target: Distinct Subsequences (LeetCode 115). `ways[j]` counts the ways to spell `t[:j]` from the letters of `s` read so far. The empty prefix is spelled once, by picking nothing, so `ways[0] = 1`.

Boundary Model: Topologically Ordered Subproblem Recurrence (DAG(Directed Acyclic Graph))

Optimal substructure: DP state dp[i] depends strictly on already-computed subproblems. Rolling array reduces space from O(S) to O(1 tier).

Loop Invariant Termination

Iterate base cases -> compute states in topological transition order (dp[i] = min/max/sum of transitions).

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🧵 The Analogy: Threading Beads in Order

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

ways = [1] + [0] * n
for ch in s:
    for j in range(n, 0, -1):
        if t[j - 1] == ch:
            ways[j] += ways[j - 1]
return ways[n]

💡 Summary

Running j forwards: for j in range(n, 0, -1) runs from n down. Going up, ways[j - 1] already includes the current ch, so one letter of s fills two places of t: "rabbbit", "rabbit" returns 6 instead of 3.
Replacing instead of adding: ways[j] += ways[j - 1], not =. The ways that skip ch are still valid, so "ccc", "c" needs 3, not 1.
No seed for the empty prefix: start with ways = [1] + [0] * n. The empty prefix t[:0] is spelled once, by picking nothing; with ways[0] = 0 no match can ever start.
Reading the wrong letter of t: ways[j] is the count for the prefix t[:j], whose last letter is t[j - 1]. Comparing t[j] == ch matches the next letter instead, and at j = n it runs past the end of t.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots a count of in-order picks and answers it with one running count per prefix of t.

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

for j in range(n, 0, -1), never upwards: going up, ways[j - 1] already includes the current ch, so one letter fills two places of t and "rabbbit", "rabbit" returns 6 instead of 3.
ways[j] += ways[j - 1], not =: the ways that skip ch stay valid, and "ccc", "c" needs 3, not 1.
ways = [1] + [0] * n: the empty prefix is spelled once, by picking nothing; starting ways[0] at 0 makes every count 0.
Don't recurse on (position in s, position in t) without saving results: the same pairs are solved again and again, exponential in the length of s. The running counts solve each pair once.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use Subsequence Counting DP. Every character of s is either skipped or used as the next letter of t, so I keep one count per prefix of t: ways of j is the number of ways to spell the first j letters with what I've read so far. ways of zero is one, the empty prefix. For each character of s, I walk j from n down to one, and where t of j minus one equals that character, I add ways of j minus one into ways of j. The old value counts the ways that skip the character, and the added value counts the ways that finish with it. Walking j backwards is the trap it avoids: going up, ways of j minus one would already include this same character, and one letter of s would fill two places of t. The answer is ways of n. That's O(M times N) time and O(N) space.

So: ways[j] per prefix of t, ways[0] = 1; for each ch of s, walk j from n down and add ways[j - 1] where t[j - 1] == ch.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(M * N)

SPACE COMPLEXITY

O(N)

Formal Recurrence Relation

$T(M, N) = O(N) + M \cdot N \cdot O(1) = O(M \cdot N)$

Derivation Progression

Set up the counts

O(N)

ways = [1] + [0] * n builds N + 1 counts once.

Outer loop

M iterations

for ch in s reads every character of s once.

Inner loop

N iterations per character

for j in range(n, 0, -1) visits every prefix length from N down to 1.

Loop body

O(1)

One comparison t[j - 1] == ch and at most one addition ways[j] += ways[j - 1].

Total

O(M * N)

M characters times N prefixes, constant work each; the answer is read from ways[n].

Variable Definitions

$M$

Length of s, the string the letters are picked from

$N$

Length of t, the string to spell (n = len(t) in the code)

Memory Architecture & Bounds

🟣 Call Stack

O(1): iterative, no recursion

🔵 Auxiliary Heap

O(N): the ways list of N + 1 counts

🟢 Output Space

O(1): one integer

Boundary Best / Worst Cases

Best Case

$O(M \cdot N)$ : the inner loop runs over every j even when no letter matches

Average Case

$O(M \cdot N)$

Worst Case

$O(M \cdot N)$

State-Space & Subproblem DAG(Directed Acyclic Graph) Topology

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

1. One Count per Prefix of t

After each character of `s`, `ways[j]` is the number of ways to spell `t[:j]` with the characters read so far, and `ways[0] = 1`: the empty prefix is spelled once, by picking nothing.

2. Skip or Use, Read Before Writing

3. One Row, M x N Steps

Each of the M characters walks the N prefixes once with O(1) work, and the counts live in one row that is overwritten in place: O(M * N) time and O(N) space.

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: DISTINCT SUBSEQUENCES (LEETCODE 115)

T = O(M * N)S = O(N)

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
One count per prefix of t	`ways = [1] + [0] * n`	`ways[j]` counts the ways to spell `t[:j]` from the letters of `s` read so far. The empty prefix is spelled once, by picking nothing, so `ways[0] = 1`.
Read s one character at a time	`for ch in s:`	Each character is either used for one place of `t` or skipped; the counts before it already hold every way to use the earlier characters.
Walk the prefixes backwards (the trap)	`for j in range(n, 0, -1):`	`ways[j]` reads `ways[j - 1]`. Going from `n` down means `ways[j - 1]` has not been touched by this `ch` yet, so one letter of `s` never fills two places of `t`.
Use ch for t[j - 1] only when they match	`if t[j - 1] == ch: ways[j] += ways[j - 1]`	The old `ways[j]` are the ways that skip `ch`; each of the `ways[j - 1]` ways can finish `t[:j]` with `ch`. Adding keeps both.
Answer: the count for the whole of t	`return ways[n]`	After the last character of `s`, `ways[n]` counts every way to spell all of `t`.

Step

ch

Updates (j from 6 down to 1)

ways after the row

Start

ways = [1] + [0] * 6

[1, 0, 0, 0, 0, 0, 0]

r

ways[1] += ways[0]: 0 + 1 = 1

[1, 1, 0, 0, 0, 0, 0]

a

ways[2] += ways[1]: 0 + 1 = 1

[1, 1, 1, 0, 0, 0, 0]

b

ways[4] += ways[3]: 0 + 0 = 0, then ways[3] += ways[2]: 0 + 1 = 1

[1, 1, 1, 1, 0, 0, 0]

b

ways[4] += ways[3]: 0 + 1 = 1, then ways[3] += ways[2]: 1 + 1 = 2

[1, 1, 1, 2, 1, 0, 0]

b

ways[4] += ways[3]: 1 + 2 = 3, then ways[3] += ways[2]: 2 + 1 = 3

[1, 1, 1, 3, 3, 0, 0]

i

ways[5] += ways[4]: 0 + 3 = 3

[1, 1, 1, 3, 3, 3, 0]

t

ways[6] += ways[5]: 0 + 3 = 3

[1, 1, 1, 3, 3, 3, 3]

End

return ways[6]

Step

ch

Updates (j from 6 down to 1)

ways after the row

Start

ways = [1] + [0] * 6

[1, 0, 0, 0, 0, 0, 0]

r

ways[1] += ways[0]: 0 + 1 = 1

[1, 1, 0, 0, 0, 0, 0]

a

ways[2] += ways[1]: 0 + 1 = 1

[1, 1, 1, 0, 0, 0, 0]

b

ways[4] += ways[3]: 0 + 0 = 0, then ways[3] += ways[2]: 0 + 1 = 1

[1, 1, 1, 1, 0, 0, 0]

b

ways[4] += ways[3]: 0 + 1 = 1, then ways[3] += ways[2]: 1 + 1 = 2

[1, 1, 1, 2, 1, 0, 0]

b

ways[4] += ways[3]: 1 + 2 = 3, then ways[3] += ways[2]: 2 + 1 = 3

[1, 1, 1, 3, 3, 0, 0]

i

ways[5] += ways[4]: 0 + 3 = 3

[1, 1, 1, 3, 3, 3, 0]

t

ways[6] += ways[5]: 0 + 3 = 3

[1, 1, 1, 3, 3, 3, 3]

End

return ways[6]

🧭 Conceptual Foundation & Pattern Intuition

🧵 The Analogy: Threading Beads in Order

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

ways = [1] + [0] * n
for ch in s:
    for j in range(n, 0, -1):
        if t[j - 1] == ch:
            ways[j] += ways[j - 1]
return ways[n]

💡 Summary

Canonical Invariant

Concrete Code

Engineering Rationale

One count per prefix of t

ways = [1] + [0] * n

`ways[j]` counts the ways to spell `t[:j]` from the letters of `s` read so far. The empty prefix is spelled once, by picking nothing, so `ways[0] = 1`.

Read s one character at a time

for ch in s:

Each character is either used for one place of `t` or skipped; the counts before it already hold every way to use the earlier characters.

Walk the prefixes backwards (the trap)

for j in range(n, 0, -1):

`ways[j]` reads `ways[j - 1]`. Going from `n` down means `ways[j - 1]` has not been touched by this `ch` yet, so one letter of `s` never fills two places of `t`.

Use ch for t[j - 1] only when they match

if t[j - 1] == ch:
    ways[j] += ways[j - 1]

The old `ways[j]` are the ways that skip `ch`; each of the `ways[j - 1]` ways can finish `t[:j]` with `ch`. Adding keeps both.

Answer: the count for the whole of t

return ways[n]

After the last character of `s`, `ways[n]` counts every way to spell all of `t`.