115. Distinct Subsequences
Difficulty: Hard | Published on 2026-09-07
This is a genuinely hard problem because it introduces Dynamic Programming (DP) for the first time in this series — a big, important new tool. Let's build it up very carefully from zero.
1. Problem in Very Simple Language
You're given two strings: INLINECODE0 (the "source" string) and INLINECODE1 (the "target" string).
A subsequence of INLINECODE2 is what you get by deleting zero or more characters from INLINECODE3, without rearranging the remaining characters — they must stay in their original left-to-right order, just with some characters possibly skipped.
Your job: count how many different ways you can pick characters out of INLINECODE4 (in order, skipping some) so that the characters you picked, read in order, spell out exactly INLINECODE5.
Two "ways" count as different if they use characters from different positions in INLINECODE6, even if the actual letters picked look identical when written out.
What's given: two strings, INLINECODE7 and INLINECODE8. What to find: the number of distinct ways to select a subsequence of INLINECODE9 that equals INLINECODE10, letter for letter. What to return: that count, as an integer.
2. Real-Life Analogy
Imagine INLINECODE11 is a long row of numbered raffle tickets, each with a letter printed on it, like INLINECODE12. You want to find every possible way to walk along this row, from left to right, tapping some tickets (and skipping others), such that the letters on the tickets you tapped spell out the word INLINECODE13.
Since there are three INLINECODE14 tickets in a row, when you need "just one b" for your spelling, you could tap any one of those three INLINECODE15 tickets — and each different choice of which ticket you tapped counts as a genuinely different way, even though the final spelled word looks the same on paper. You want to count the total number of distinct "which tickets did I tap" plans that successfully spell INLINECODE16.
3. Important Programming Concepts I Need First
String and Character Indexing
Concept: A string is a sequence of characters; INLINECODE17 gets the character at position INLINECODE18 (0-indexed). Example: For INLINECODE19, INLINECODE20, INLINECODE21. Why we need it: We'll be comparing individual characters of INLINECODE22 and INLINECODE23 constantly.Subsequence (vs. Substring — an important distinction!)
Concept: A substring must be continuous (no gaps). A subsequence can skip characters, as long as the remaining ones keep their relative order. Example: For INLINECODE24: INLINECODE25 is a valid subsequence (skip the INLINECODE26) but NOT a valid substring (there's a gap). INLINECODE27 is both a valid substring and a valid subsequence. Why we need it: This entire problem is about subsequences, not substrings — mixing these up leads to a completely different (and wrong) problem.Recursion
Concept: A function that solves a problem by calling itself on a smaller version of the same problem, until it reaches a case simple enough to answer directly (a "base case"). Simple Example: To compute "how many ways can I climb INLINECODE28 stairs, taking 1 or 2 steps at a time," you can express it as: INLINECODE29, with base cases INLINECODE30 and handling small INLINECODE31 directly. Why we need it: Counting "ways to match INLINECODE32 using a prefix of INLINECODE33" naturally breaks down into smaller versions of the exact same question — a textbook signal for recursion.Overlapping Subproblems (a key idea behind DP)
Concept: Sometimes, when solving a problem recursively, the exact same smaller sub-question gets asked over and over again, through different recursive paths. If we don't remember the answer, we end up recomputing it repeatedly — wasteful. Example: In the classic Fibonacci recursion, INLINECODE34 calls INLINECODE35 and INLINECODE36; but INLINECODE37 also ends up calling INLINECODE38 again, from a different branch — same question, asked twice. Why we need it: As we'll see, this problem's recursion re-asks identical questions many, many times — recognizing this is what motivates the next concept.Memoization
Concept: The fix for overlapping subproblems: the first time you compute the answer to some specific sub-question, save it somewhere (like a lookup table). Every subsequent time that exact same sub-question comes up, just look up the saved answer instantly instead of recomputing it. Why we need it: This turns an otherwise extremely slow recursive solution into a fast one, by ensuring every distinct sub-question is only ever actually computed once.Dynamic Programming (DP) — 2D Table
Concept: Dynamic Programming is a general strategy: instead of recursion-with-memoization (computing top-down, saving answers as you go), you can often build the same answers bottom-up, filling in a table (often 2D, when there are two changing quantities — here, "how far into INLINECODE39" and "how far into INLINECODE40") in a carefully chosen order, so that whenever you need a smaller answer, it's already sitting in the table, precomputed. Simple Example: A table INLINECODE41 where INLINECODE42 represents "the answer to the problem using only the first INLINECODE43 characters of INLINECODE44 and the first INLINECODE45 characters of INLINECODE46." You fill it in starting from the smallest INLINECODE47 and build up. Why we need it: This problem's natural recursive structure depends on two shrinking quantities (position in INLINECODE48, position in INLINECODE49) — a perfect match for a 2D DP table.2D Array
Concept: A grid of values, indexed by two numbers (row and column), like INLINECODE50. Why we need it: Our DP table has one dimension per string.4. Understand the Input
Take Example 1: CODEBLOCK0
INLINECODE51 has 7 characters: INLINECODE52 (positions 0 through 6). Note the three INLINECODE53s in a row (positions 2, 3, 4). INLINECODE54 has 6 characters: INLINECODE55 (positions 0 through 5). Note INLINECODE56 needs two INLINECODE57s. We want: how many different ways can we choose 6 positions from INLINECODE58 (in increasing order) such that the characters at those positions, in order, spell exactly INLINECODE59? Why do the three INLINECODE60s in INLINECODE61 matter so much? Because INLINECODE62 needs exactly 2 INLINECODE63s in a row (conceptually), and there are INLINECODE64 available INLINECODE65s to choose INLINECODE66 from — this is exactly where the "3 different ways" in the answer comes from, as we'll see.
5. Understand the Output
Output: INLINECODE67
The three ways (matching the problem's illustration) are essentially: use INLINECODE68 at position 2 and INLINECODE69 at position 3; use INLINECODE70 at position 2 and INLINECODE71 at position 4; use INLINECODE72 at position 3 and INLINECODE73 at position 4. (The INLINECODE74, INLINECODE75, INLINECODE76, INLINECODE77 all come from their own unique single positions in INLINECODE78, so they don't add extra choices — only which two of the three INLINECODE79s is genuinely ambiguous.) Each of these 3 choices produces a different set of positions used, even though the resulting spelled-out word is identical (INLINECODE80) in every case — remember, we're counting distinct selections, not distinct spellings.
6. Solve the Example Manually
Let's build understanding with a much smaller example first, since the real one has a lot of moving parts: INLINECODE81, INLINECODE82.
We want: how many ways to pick 2 positions (in order) out of the 3 INLINECODE83s in INLINECODE84, such that both picked characters equal INLINECODE85 (trivially true here, since all characters are INLINECODE86)?
This is really just: "how many ways to choose 2 positions out of 3, keeping their relative order" — which is the same as asking "how many 2-element subsets of INLINECODE87 are there" (order is automatically preserved when we just pick a subset and read left to right). That's INLINECODE88 — 3 ways. This matches our intuition!
Now here's the key manual insight, thinking recursively: to match INLINECODE89 using INLINECODE90, look at the last character of INLINECODE91 (position 2, a INLINECODE92) and the last character of INLINECODE93 (also INLINECODE94).
Since they match, we have two options for this last INLINECODE95 in INLINECODE96: Use it to match the last INLINECODE97 of INLINECODE98 — then we still need to match the remaining INLINECODE99 (INLINECODE100, just 1 character) using the remaining INLINECODE101 (INLINECODE102, positions 0-1). Skip it (don't use this INLINECODE103 character at all) — then we still need to match the full INLINECODE104 (INLINECODE105) using the remaining INLINECODE106 (INLINECODE107, positions 0-1, i.e., everything except the last character).
So: INLINECODE108.
We'd keep breaking this down the same way until we hit trivial base cases (like "matching an empty INLINECODE109 is always possible in exactly 1 way — just pick nothing," or "matching a non-empty INLINECODE110 using an empty INLINECODE111 is impossible, 0 ways"). Let's not fully expand this by hand (that's what code is for!), but this recursive breaking-down is exactly the algorithm we're about to formalize.
7. Think Like a Programmer
What do I know? For any given "remaining piece of INLINECODE112" and "remaining piece of INLINECODE113," I can look at their last characters and reason about matching options. What do I need to find? The total count of valid subsequence selections. What can I try? Define a function INLINECODE114 = "number of ways to form INLINECODE115 (the first INLINECODE116 characters of INLINECODE117) using INLINECODE118 (the first INLINECODE119 characters of INLINECODE120)." We want INLINECODE121. What's the recursive breakdown? Look at the last character of the current INLINECODE122-prefix (i.e., INLINECODE123) and the last character of the current INLINECODE124-prefix (INLINECODE125): If INLINECODE126 (they match): we have two choices — use this INLINECODE127 character to match this INLINECODE128 character (then recurse on INLINECODE129), OR don't use it at all (recurse on INLINECODE130). Total: INLINECODE131. If they don't match: we have no choice but to skip this INLINECODE132 character (it can't help match INLINECODE133's last character) — so it's just INLINECODE134. What are the base cases? If INLINECODE135 (we've matched all of INLINECODE136 already, nothing left needed): there's exactly 1 way (pick nothing further) — this holds regardless of what INLINECODE137 is (even matching "nothing" using "nothing" is 1 way — the empty selection). If INLINECODE138 but INLINECODE139 (we still need characters, but INLINECODE140 has run out): 0 ways — impossible. What happens if I implement this recursion directly? It will be correct, but as hinted in Section 3, it will likely repeat identical sub-questions INLINECODE141 many times through different recursive paths — leading to extremely slow performance. Can I make it faster? Yes — since INLINECODE142 only ever depends on INLINECODE143 and INLINECODE144, and there are only INLINECODE145 possible combinations of these two numbers, we can memoize (remember every answer we've computed) or, even more directly, build a 2D DP table bottom-up. What information should I remember? A 2D table INLINECODE146 storing exactly the answer to INLINECODE147 for every INLINECODE148 from INLINECODE149 to INLINECODE150, and every INLINECODE151 from INLINECODE152 to INLINECODE153.
8. Start With the Brute Force Solution
Brute force idea: Implement the recursive INLINECODE154 function exactly as reasoned in Section 7, with no memoization at all — just plain recursion.
Why it works: It directly implements the correct recursive logic: at each step, either use the matching character (if it matches) or skip the current INLINECODE155 character.
Why it's correct: Every possible subsequence selection corresponds to a sequence of "use it" / "skip it" decisions as we walk through INLINECODE156 from the end backward (or equivalently, front-to-back) — the recursion explores exactly this decision tree, and the base cases correctly terminate it.
CODEBLOCK1
CODEBLOCK2
Time complexity: In the worst case, this recursion can branch into up to INLINECODE157 calls (every character has an independent "use or skip" decision when characters keep matching), giving roughly INLINECODE158 time — catastrophically slow for INLINECODE159 and INLINECODE160 up to length INLINECODE161.
Space complexity: INLINECODE162 for the recursion call stack depth (not counting the exponential blow-up in total calls made).
9. Explain the Brute Force Code Line by Line
INLINECODE163 — kicks off the recursion asking "how many ways to match the entire INLINECODE164 using the entire INLINECODE165?" INLINECODE166 — base case: if there's nothing left of INLINECODE167 to match, there's exactly one way to "match nothing" — do nothing further. This is true no matter how much of INLINECODE168 remains. INLINECODE169 — base case: if INLINECODE170 has run out but INLINECODE171 still needs INLINECODE172 more characters, it's simply impossible — 0 ways. INLINECODE173 — compares the last character of the current INLINECODE174-prefix to the last character of the current INLINECODE175-prefix. (We look at the end of each prefix because that's the natural "next decision" as we shrink both prefixes from full length down to 0 — though you could equally reason from the front; both give the same final count.) INLINECODE176 — if they match, we ADD both options together: "use this character" (both prefixes shrink) plus "skip this character" (only the INLINECODE177 prefix shrinks, INLINECODE178's requirement stays the same). INLINECODE179 (the INLINECODE180 branch) — if they don't match, our only option is to skip this INLINECODE181 character (it's structurally impossible for it to help match INLINECODE182's last needed character), so we just shrink INLINECODE183.
10. Why Is the Brute Force Solution Not Ideal?
Imagine INLINECODE184 and INLINECODE185 are each 1000 characters long, and many characters happen to match repeatedly (like lots of the same letter). The recursion tree can branch exponentially — potentially trillions upon trillions of recursive calls, most of which are asking the exact same question (INLINECODE186 for some specific INLINECODE187 pair) over and over again through different paths. With only about INLINECODE188 distinct possible INLINECODE189 pairs total, but potentially astronomically more repeated calls to the same pairs, this is a massive amount of wasted, duplicate work.
11. Find the Better Approach
"Can we avoid recomputing the same sub-question over and over?"
Yes — since INLINECODE190 only ever depends on the two numbers INLINECODE191 and INLINECODE192, and there are only about a million distinct combinations of them (for lengths up to 1000), we should compute each distinct INLINECODE193 answer exactly once, and reuse it every time it's needed again.
CODEBLOCK3
⭐ Key Insight
Before the insight
The recursive definition is correct, but it recomputes identical INLINECODE194 sub-questions an enormous number of times, since the same smaller prefix-lengths get reached via many different sequences of "use/skip" decisions.The problem
Recomputing the same answer over and over is pure waste — if we could just remember each INLINECODE195 answer the first time we compute it, all the repeated recursive calls would become instant lookups instead.The insight
INLINECODE196 — the number of ways to match the first INLINECODE197 characters of INLINECODE198 using the first INLINECODE199 characters of INLINECODE200 — depends ONLY on the values of INLINECODE201 and INLINECODE202, nothing else. This means we can organize all possible INLINECODE203 answers into a simple 2D table, and fill it in systematically: start with the smallest, simplest cases (INLINECODE204 or INLINECODE205, which we know directly), and build up to larger INLINECODE206 using the same recurrence relation from Section 7 — but now, every smaller answer we need is already sitting in the table, computed exactly once.After the insight
The exponential blow-up completely disappears. We do a fixed, predictable amount of work — one table cell at a time — for a total of INLINECODE207 cells, each taking small, constant-time work to fill in.13. Dry Run the Optimized Solution
Let's dry-run a small case: INLINECODE208, INLINECODE209 (chosen to be small but still illustrate the mechanics, closely related to Example 2's INLINECODE210 piece).
We build a table INLINECODE211, where INLINECODE212 ranges INLINECODE213 (length of INLINECODE214) and INLINECODE215 ranges INLINECODE216 (length of INLINECODE217). INLINECODE218 = ways to form the first INLINECODE219 characters of INLINECODE220 using the first INLINECODE221 characters of INLINECODE222.
Base row (INLINECODE223): matching "nothing" is always 1 way, regardless of INLINECODE224. So INLINECODE225.
Base column (INLINECODE226, INLINECODE227): matching something using no characters of INLINECODE228 is always impossible: INLINECODE229.
Now fill in the rest, row by row (INLINECODE230 from 1 to 3), left to right (INLINECODE231 from 1 to 2). Recall INLINECODE232 means INLINECODE233. And INLINECODE234 means INLINECODE235.
| i (using s[0..i-1]) | j=1 (t[0..0]="a") | j=2 (t[0..1]="ag") |
|---|---|---|
| 0 | 0 | 0 |
| 1 (s="b") | ? | ? |
| 2 (s="ba") | ? | ? |
| 3 (s="bag") | ? | ? |
Row i=2 (s prefix = "ba", last char s[1]='a'): INLINECODE244: compare INLINECODE245 to INLINECODE246 — match! So INLINECODE247. INLINECODE248: compare INLINECODE249 to INLINECODE250 — no match. So INLINECODE251.
Row i=3 (s prefix = "bag", last char s[2]='g'): INLINECODE252: compare INLINECODE253 to INLINECODE254 — no match. So INLINECODE255. INLINECODE256: compare INLINECODE257 to INLINECODE258 — match! So INLINECODE259.
Final answer: INLINECODE260. Indeed, INLINECODE261 contains INLINECODE262 as a subsequence in exactly 1 way (positions 1 and 2). ✔️ Makes sense — there's only one INLINECODE263 and one INLINECODE264 in INLINECODE265, so no ambiguity.
14. Optimized Code
CODEBLOCK4
CODEBLOCK5
15. Explain Optimized Code Line by Line
INLINECODE266 — store both lengths for convenience. INLINECODE267 — create our 2D table. We use size INLINECODE268 and INLINECODE269 (not just INLINECODE270 and INLINECODE271) so that we have a valid row/column for representing "using zero characters" of each string — this is a very common DP setup trick, giving us room for the base cases. The INLINECODE272 loop — fills in the entire "matching an empty INLINECODE273" column: no matter how much of INLINECODE274 we're allowed to use (including none at all), there's always exactly 1 way to match "nothing" (just don't pick anything). We don't need an explicit loop for INLINECODE275 (for INLINECODE276) because Java automatically initializes all INLINECODE277 array entries to INLINECODE278 by default — this is exactly the value we want there anyway. The nested INLINECODE279 loops — fill in the rest of the table, row by row (increasing INLINECODE280), and within each row, column by column (increasing INLINECODE281). This order guarantees that whenever we compute INLINECODE282, the values INLINECODE283 and INLINECODE284 it depends on have already been computed in a previous row. INLINECODE285 — note the INLINECODE286: since INLINECODE287 represents using the first INLINECODE288 characters of INLINECODE289 (indices INLINECODE290 to INLINECODE291), the "current"/"last" character being considered is at index INLINECODE292, not INLINECODE293. Same idea for INLINECODE294. INLINECODE295 — if the characters match: add the "use this character" count (INLINECODE296, both prefixes shrink) and the "skip this character" count (INLINECODE297, only INLINECODE298's prefix shrinks). INLINECODE299 (in the INLINECODE300) — if they don't match, we're forced to skip this INLINECODE301 character; the count is exactly whatever it was without this character available. INLINECODE302 — after filling the entire table, the answer to the original question ("match the full INLINECODE303 using the full INLINECODE304") is sitting at INLINECODE305.
16. Test With Multiple Examples
Example 1 — Normal Case
INLINECODE306. Building the full INLINECODE307 table by hand is tedious, but following the exact same mechanics as the dry run in Section 13 (matching characters trigger the "add both options" rule; the three consecutive INLINECODE308s in INLINECODE309 against the two needed INLINECODE310s in INLINECODE311 is exactly where the branching that produces "3" comes from) → Output: INLINECODE312 ✔️Example 2 — Different Case
INLINECODE313 → following the same table-filling process → Output: INLINECODE314 ✔️ (This example has more structural ambiguity than Example 1 — there are two separate INLINECODE315s that could each pair with either of two INLINECODE316s and so on, compounding into 5 total distinct selections.)Example 3 — Edge Case (t longer than s)
INLINECODE317. Here INLINECODE318. It's structurally impossible to select 3 characters from a string of only 2 characters. Following the algorithm: eventually INLINECODE319 would need contributions from INLINECODE320 and INLINECODE321, both of which trace back to needing more INLINECODE322-characters than INLINECODE323 allows — everything bottoms out at INLINECODE324. Output: INLINECODE325 (matches intuition — impossible when INLINECODE326 is longer than INLINECODE327).17. Edge Cases
INLINECODE328 longer than INLINECODE329 → answer is always INLINECODE330 (impossible to pick more characters than exist). INLINECODE331 is empty — not possible per the given constraints (INLINECODE332), but conceptually, this would trivially be INLINECODE333 way (matching nothing). INLINECODE334 and INLINECODE335 are identical → there's exactly INLINECODE336 way (use every character of INLINECODE337, no choices possible anywhere along the way). INLINECODE338 has no characters matching INLINECODE339 at all → answer is INLINECODE340 (the INLINECODE341 table's matching branches never trigger; everything just cascades down to INLINECODE342, and since INLINECODE343 for any INLINECODE344, everything stays INLINECODE345). Long runs of the same repeated character in both INLINECODE346 and INLINECODE347 (like Example 1's INLINECODE348 vs INLINECODE349) → this is exactly where the "add both options" branch does real, non-trivial work, producing counts bigger than 1. Very large strings (INLINECODE350 up to INLINECODE351 each) → our INLINECODE352 DP table has up to INLINECODE353 million cells — very manageable, unlike the brute force's exponential blow-up. Answer could be large, but fits in a 32-bit signed integer — the problem statement guarantees this, so plain INLINECODE354 arithmetic (no overflow concerns) is safe as specified.18. Time Complexity
What is time complexity? It's a way of estimating how the total work grows as input size grows, using a general trend rather than a stopwatch.
CODEBLOCK6
Why: In the DP version, we fill in each of the INLINECODE355 table cells exactly once, and computing each cell takes only a small, constant amount of work (one character comparison, one or two additions). For INLINECODE356, that's about INLINECODE357 million cells — each cheap — totaling roughly a million basic operations, which any modern computer handles in a tiny fraction of a second. Compare this to the brute force's potential INLINECODE358 calls — a number so astronomically large it's meaningless to even compare directly to "a million"; DP transforms an utterly infeasible computation into a trivially fast one.
19. Space Complexity
The INLINECODE359 table has INLINECODE360 entries, each a plain INLINECODE361.
So extra space used is INLINECODE362 — for INLINECODE363, that's about 1 million integers, comfortably within typical memory limits. (As a further optimization, since each row INLINECODE364 only ever depends on row INLINECODE365, you could shrink this to INLINECODE366 space by keeping just "the previous row" and "the current row" — but the full 2D table, as shown here, is clearer for learning and is already efficient enough for this problem's constraints.)
20. Common Mistakes Beginners Make
❌ "A subsequence must be a continuous block of characters." ✅ That's a substring, not a subsequence. A subsequence can skip characters, as long as the remaining ones keep their relative left-to-right order. ❌ "Since the final spelled-out result looks the same, different selections using the same set of characters shouldn't count separately." ✅ The problem explicitly counts distinct selections (which specific positions in INLINECODE367 were used), not distinct-looking output strings — this is exactly why repeated characters (like the three INLINECODE368s) create multiple valid counts even though they "look the same" once spelled out. ❌ "If the characters don't match, I should still consider 'using' this INLINECODE369 character somehow." ✅ If INLINECODE370, that INLINECODE371 character cannot possibly be the one matching INLINECODE372's current needed character — the only sensible option is to skip it, i.e., INLINECODE373. ❌ "When characters DO match, I should only take the 'use it' option (INLINECODE374), since that seems like the more direct match." ✅ You must ALSO include the 'skip it' option (INLINECODE375), even when characters match — because a later matching character in INLINECODE376 might be the one this particular position in INLINECODE377 should actually pair with, in a different valid selection. Forgetting this "skip it" addition undercounts the true number of ways (this is precisely why problems like Example 1, with repeated INLINECODE378s, have more than 1 answer). ❌ "I'll just implement the recursive definition directly and hope it's fast enough." ✅ For strings up to length 1000, plain recursion without memoization is exponentially too slow — you must use the 2D DP table (or equivalent memoized recursion) to make this run in reasonable time.
21. How to Recognize This Pattern in Other Problems
Watch for these signal phrases:
CODEBLOCK7
Whenever you're comparing two sequences and need to count ways (or find some optimal value) based on how their characters align, and you notice the direct recursive definition re-asks the same INLINECODE379 sub-question repeatedly, think: 2D DP table, indexed by position in each sequence.
22. Interview Thinking
CODEBLOCK8
Applied here: the "aha" is recognizing that the brute-force recursion's shape was already exactly right — the only problem was re-doing identical work; converting it into a systematically-filled table removes all the waste while keeping the exact same logic.
23. Mini Challenge
Try these before checking the answers:
1. Why do we need INLINECODE380 for every INLINECODE381, rather than just INLINECODE382? 2. If INLINECODE383, why is it wrong to write INLINECODE384 instead of INLINECODE385? 3. In Example 1 (INLINECODE386), which specific cell(s) in the DP table would you expect to show the branching factor of "3," and roughly why?
Answer to Mini Challenge
1. INLINECODE387 represents "using the first INLINECODE388 characters of INLINECODE389 to match an empty INLINECODE390" — this is possible in exactly 1 way (select nothing) regardless of how many characters of INLINECODE391 are available, since you're never forced to use any of them. Only setting INLINECODE392 would leave every other INLINECODE393 at its default INLINECODE394, which would incorrectly suggest it's impossible to "match nothing" once INLINECODE395 has any characters at all. 2. INLINECODE396 represents "one character was successfully consumed from both INLINECODE397 and INLINECODE398," which is only valid when those two characters actually matched. If they didn't match, pretending they did (by using INLINECODE399) would incorrectly count selections where a mismatched character was used to fill a spot in INLINECODE400 it can't actually spell correctly. The correct move when they don't match is to skip the INLINECODE401 character entirely, i.e., INLINECODE402 (t's requirement is unchanged, only s's available prefix shrinks). 3. The branching happens around the cells corresponding to the three INLINECODE403s in INLINECODE404 (positions 2, 3, 4) each being checked against INLINECODE405's INLINECODE406 positions — every time INLINECODE407 triggers the "add both options" rule, it's compounding possibilities from the multiple available INLINECODE408s; by the time the table reaches the cell corresponding to "all of s" and "all of t," these compounding additions accumulate to exactly INLINECODE409.
24. Final Revision
🧠 Problem in One Sentence
Count the number of distinct ways to select a subsequence of INLINECODE410 (preserving order) that exactly equals INLINECODE411.🔑 Main Idea
Define INLINECODE412 = ways to form the first INLINECODE413 characters of INLINECODE414 using the first INLINECODE415 characters of INLINECODE416; if the current characters match, add both the "use it" and "skip it" options; otherwise, only "skip it" is possible — fill this table bottom-up to avoid the brute force's exponential repeated work.⚙️ Algorithm
1. Create a INLINECODE417 table INLINECODE418. 2. Set INLINECODE419 for all INLINECODE420 (matching empty INLINECODE421 is always 1 way); leave INLINECODE422 for INLINECODE423 (default). 3. For each INLINECODE424 from 1 to INLINECODE425, each INLINECODE426 from 1 to INLINECODE427: if INLINECODE428, INLINECODE429; otherwise INLINECODE430. 4. Return INLINECODE431.⏱️ Complexity
Time: INLINECODE432- Space: INLINECODE433 (reducible to INLINECODE434 with a rolling-row optimization)
🎯 Pattern to Remember
Two-sequence "count the ways" or "find the optimal alignment" problems, where naive recursion re-asks identical INLINECODE435 sub-questions, call for a 2D DP table indexed by position in each sequence.25. Beginner Quiz
1. (Understanding) What's the difference between a subsequence and a substring, and why does that distinction matter for this problem? 2. (Basic concept) What does INLINECODE436 represent in our table, in plain words? 3. (Logic) Why do we ADD two values together (INLINECODE437) specifically when the current characters match, rather than just picking one of them? 4. (Dry run) For INLINECODE438, INLINECODE439, build the small DP table by hand and find the final answer. (Hint: how many single INLINECODE440s could you "choose" from INLINECODE441?) 5. (Complexity/pattern) Why does the brute-force recursive solution become exponentially slow, and what specific property of INLINECODE442 (mentioned in the Key Insight) is what allows the DP table to fix this?