940. Distinct Subsequences II

Difficulty: Hard | Published on 2026-09-07

This problem is a different flavor of "count subsequences" than #115 — here there's only one string, and the whole challenge is avoiding double-counting duplicates. It introduces a new, very elegant DP trick. Let's build it from zero.

1. Problem in Very Simple Language

You're given a single string INLINECODE0.

A subsequence is what you get by deleting zero or more characters from INLINECODE1 (without rearranging what's left) — so the remaining characters still appear in their original left-to-right order.

Different positions deleted can sometimes produce the exact same resulting string. For example, in INLINECODE2, picking "the INLINECODE3 at position 0" gives you the string INLINECODE4, and picking "the INLINECODE5 at position 2" also gives you the string INLINECODE6 — these are the same subsequence value, even though they came from different positions.

Your job: count how many distinct (i.e., different-looking) non-empty subsequence strings can be formed from INLINECODE7 — counting each unique resulting string only once, no matter how many different ways there are to produce it.

Since this count can get huge, return it modulo INLINECODE8 (a big prime number used to keep the answer within normal integer range).

What's given: a string INLINECODE9. What to find: the number of distinct non-empty subsequence strings. What to return: that count, mod INLINECODE10.

2. Real-Life Analogy

Imagine a bag of scrabble tiles laid out in a row, spelling INLINECODE11. You can pick any subset of tiles (keeping their left-to-right order) to spell a "mini-word." The catch: if two different picks spell out the exact same mini-word (like picking the 1st tile vs. the 3rd tile, both letter INLINECODE12), that only counts as one distinct mini-word in your final tally, not two. You want the total number of genuinely different-looking mini-words you could spell this way (not counting the empty word).

3. Important Programming Concepts I Need First

Subsequence (recap from #115)
Concept: Delete some characters, keep the rest in order. Why we need it: Same core definition as before — but now we're comparing subsequences to each other for equality, not comparing against a fixed target string.
Distinctness / Deduplication
Concept: Counting only unique results, even when multiple different processes could produce the same result. Example: If both "pick position 0" and "pick position 2" give you the string INLINECODE13, that's one distinct result, not two. Why we need it: This is the entire crux of the problem — #115 counted ways, this problem counts distinct results.

Modulo Arithmetic

Concept: INLINECODE14 gives the remainder when INLINECODE15 is divided by INLINECODE16. When numbers in a calculation could get astronomically large, we take INLINECODE17 at every step to keep numbers small and manageable, while still being able to reconstruct "the answer, if it were computed exactly, then reduced mod m at the very end" — because modulo is compatible with addition (INLINECODE18). Example: INLINECODE19. Also, INLINECODE20 — same answer either way. Why we need it: The true count of distinct subsequences can grow exponentially with string length (up to 2000 characters!) — far too big for a normal integer — so we must take INLINECODE21 throughout, as the problem explicitly asks.
Array indexed by letter (a "26-box" array)
Concept: Since there are only 26 lowercase English letters, we can use a small fixed-size array of length 26, where index INLINECODE22 represents INLINECODE23, index INLINECODE24 represents INLINECODE25, ..., index INLINECODE26 represents INLINECODE27. We convert a character to its index using INLINECODE28. Example: INLINECODE29, so INLINECODE30 maps to index 2. Why we need it: We'll track, for each letter, some running count associated specifically with subsequences that end in that letter.

Dynamic Programming (recap from #115), applied differently here

Concept: Build up the answer incrementally, one character of INLINECODE31 at a time, using previously-computed smaller results — but this time, our "table" isn't 2D (indexed by two string positions); it's a small 1D array of size 26 (indexed by ending letter), updated as we scan through INLINECODE32. Why we need it: As we'll see, tracking "how many distinct subsequences end in each specific letter" turns out to be exactly the right piece of information to carry forward.

4. Understand the Input

Take Example 2: CODEBLOCK0

Characters: index 0 = INLINECODE33, index 1 = INLINECODE34, index 2 = INLINECODE35. We want: every distinct non-empty string that can be formed by deleting some characters (keeping order), counted once each. Why does having two INLINECODE36s matter? Because it creates the opportunity for duplicate results (like getting INLINECODE37 from either position 0 or position 2) — and it's exactly this duplication that the algorithm must correctly avoid over-counting.

5. Understand the Output

Output: INLINECODE38

The 6 distinct subsequences are: INLINECODE39.

Notice INLINECODE40 appears here once in this list, even though you could form the string INLINECODE41 in two different ways (using position 0's INLINECODE42, or position 2's INLINECODE43). We only count it once. Similarly, INLINECODE44 can be formed in only one way here (positions 0 and 2 — there's no other pair of INLINECODE45s), so no duplication issue there. The total number of raw ways to form subsequences (counting position-based ways separately, like problem #115's spirit) would be larger than 6 — but we specifically want distinct resulting strings, which is smaller.

6. Solve the Example Manually

Let's manually build up the distinct subsequences of INLINECODE46, one character at a time, and see how a clean formula emerges.

After processing just INLINECODE47 (first character): Distinct non-empty subsequences so far: INLINECODE48. Count = 1.

After processing INLINECODE49 (first two characters): Every subsequence we can form now either (a) doesn't use this new INLINECODE50 at all (so it's one of our old subsequences: INLINECODE51), or (b) uses this new INLINECODE52, either as "just INLINECODE53 alone" or as "some old subsequence, with INLINECODE54 appended to its end" (since INLINECODE55 is the newest, rightmost character, appending it to the end of any previously valid subsequence gives another valid subsequence).

So the new subsequences created by adding INLINECODE56 are: INLINECODE57 (b alone) and INLINECODE58 (appending b to our one existing subsequence INLINECODE59).

Combined with the old ones: INLINECODE60. Count = 3.

After processing INLINECODE61 (all three characters): Now we add the second INLINECODE62. Following the same logic: the new subsequences are "this INLINECODE63 alone" (INLINECODE64 — but wait, we already have INLINECODE65 in our set from before!) plus "every existing subsequence with this INLINECODE66 appended": INLINECODE67.

Here's the crucial subtlety: adding "this INLINECODE68 alone" would just re-create INLINECODE69, which we already have — so it does NOT add anything new to our distinct set. But the appending operations (INLINECODE70, INLINECODE71, INLINECODE72) are all brand new distinct strings we haven't seen before.

Combined set: INLINECODE73. Count = 6. ✔️ matches!

This manual walkthrough reveals the key mechanic: each new character potentially adds "itself alone" PLUS "itself appended to every existing distinct subsequence" — but we must be careful not to double-count when "itself alone" collides with something already present.

7. Think Like a Programmer

What do I know? Processing INLINECODE74 left to right, each new character can extend every subsequence formed so far, plus stand alone by itself. What do I need to find? The total count of distinct resulting strings. What can I try? Keep a running set of "all distinct subsequences formed using the prefix of INLINECODE75 processed so far." When a new character INLINECODE76 arrives, the new total set = (old set) ∪ ({ch} ∪ {every old subsequence + ch appended}). What happens if I try to literally store all these strings in a Set? With INLINECODE77 up to length 2000, the number of distinct subsequences can be enormous (up to close to INLINECODE78 in the worst case, though duplicates from repeated letters cut this down) — actually storing and comparing full strings would be catastrophically slow and memory-heavy. Can I make it faster? Yes — notice we don't actually need to know the strings themselves, just the count. And here's the beautiful trick: when a new character INLINECODE79 arrives, "itself alone" plus "itself appended to every existing subsequence" is EXACTLY equal to INLINECODE80 — because appending INLINECODE81 to every existing distinct subsequence produces that many new, still-distinct strings (they all end in INLINECODE82 now, and everything before the final INLINECODE83 was already distinct, so the whole new strings remain pairwise distinct from each other), plus the string INLINECODE84 alone is one more possibility. But what about the double-counting risk (like INLINECODE85 reappearing) seen in Section 6? This is the subtle part: if INLINECODE86 has appeared before, then some of "the new strings ending in INLINECODE87" might collide with strings we already had ending in INLINECODE88 from an earlier appearance. The fix: track, for each letter separately, how many distinct subsequences currently end in that specific letter. When INLINECODE89 shows up again, the entire previous count of "subsequences ending in INLINECODE90" gets replaced (not added to) by the new count — because every subsequence that used to end in the old INLINECODE91 can now be reformed using this newer INLINECODE92 instead (giving the identical string), so the old count becomes redundant/superseded, not something to add on top of. What information should I remember? A small array INLINECODE93, where INLINECODE94 = "number of distinct subsequences currently ending in letter INLINECODE95." The overall total distinct count is just the sum of all 26 entries.

8. Start With the Brute Force Solution

Since actually enumerating and storing every distinct subsequence string would be infeasible for INLINECODE96 up to length 2000 (astronomically many possible strings), there isn't a reasonable brute force to fully implement here the way earlier problems had one — but let's write a small-scale conceptual brute force (correct only for tiny inputs) to firmly ground the correct logic, using an actual INLINECODE97.

Brute force idea: Maintain a INLINECODE98 of all distinct subsequences seen so far. For each new character, generate "itself alone" plus "itself appended to every current set member," and add all of these into the set (a INLINECODE99 automatically handles deduplication for us).

CODEBLOCK1

CODEBLOCK2

Why it works (for small inputs): It directly simulates exactly the process described in Section 6, and relies on INLINECODE100's built-in deduplication to avoid counting the same string twice.

Time/space complexity: Both time and space are proportional to the number of distinct subsequences itself, which can be exponential in the length of INLINECODE101 — utterly infeasible once INLINECODE102 gets anywhere close to length 2000 (way too many strings to store, and each string comparison/hashing itself takes time proportional to string length).

9. Explain the Brute Force Code Line by Line

INLINECODE103 — will hold every distinct subsequence string found so far. The INLINECODE104 loop — processes each character of INLINECODE105 in order. INLINECODE106 — the new character, by itself, is always a candidate new subsequence. The inner INLINECODE107 loop — for every subsequence already found, we consider appending the new character to its end, forming a new candidate. INLINECODE108 — merge all these candidates into our running set; duplicates (strings already present) are automatically ignored by the INLINECODE109. INLINECODE110 — the final count of distinct non-empty subsequences, reduced modulo the required value.

10. Why Is the Brute Force Solution Not Ideal?

For a string like INLINECODE111 with many distinct characters, the number of distinct subsequences roughly doubles with each new distinct character (similar to counting subsets), potentially reaching close to INLINECODE112 — a number so large it dwarfs the number of atoms in the universe many times over. There's no way to store that many actual strings; we need a method that computes the count directly, without ever materializing the strings themselves.

11. Find the Better Approach

"Can we track just the COUNT, without ever storing actual strings?"

Yes — this is exactly the insight from Section 7:

CODEBLOCK3

⭐ Key Insight

Before the insight
It seems like we need to track actual subsequence strings to know which ones are duplicates of each other.
The problem
Storing strings is completely infeasible at this scale — we need a way to detect and avoid duplicates using only numbers.
The insight
Every distinct subsequence has a unique "last character used" and a unique "identity" before that last character. So if we track, separately for each of the 26 letters, "how many distinct subsequences currently end in this letter," we can compute: The grand total of all distinct subsequences = sum of all 26 INLINECODE113 values. When a new character INLINECODE114 arrives: the number of new distinct subsequences ending in INLINECODE115, as of right now, is INLINECODE116 — the INLINECODE117 accounts for "INLINECODE118 all by itself," and the INLINECODE119 accounts for "append INLINECODE120 to every distinct subsequence that existed just before this point," which (crucially) are automatically still pairwise distinct from each other once you tack the same final letter onto all of them. This freshly computed value completely replaces the old INLINECODE121 (rather than adding to it) — because any older subsequence that used to end in an earlier occurrence of INLINECODE122 can now be reproduced using this occurrence instead, making the old tally obsolete/redundant, not something to stack on top of.

After the insight

A single pass through INLINECODE123, maintaining just 26 running numbers (plus a running total), correctly and efficiently computes the exact distinct count — no strings, no exponential blow-up, no risk of double-counting.

13. Dry Run the Optimized Solution

Let's dry-run Example 3: INLINECODE124.

We maintain INLINECODE125 (all start at 0) and INLINECODE126 (which is just the sum of INLINECODE127, tracked incrementally for convenience).

Process 1st INLINECODE128: New count for subsequences ending in INLINECODE129: INLINECODE130. Update: INLINECODE131 (was 0, now replaced with 1). New total: INLINECODE132.

Process 2nd INLINECODE133: New count for subsequences ending in INLINECODE134: INLINECODE135. Update: INLINECODE136 (was 1, now replaced with 2). New total: INLINECODE137.

Process 3rd INLINECODE138: New count for subsequences ending in INLINECODE139: INLINECODE140. Update: INLINECODE141 (was 2, now replaced with 3). New total: INLINECODE142.

Final INLINECODE143. ✔️ matches (the 3 distinct subsequences are INLINECODE144, INLINECODE145, INLINECODE146)!

Notice how the "replace, don't add" rule for INLINECODE147 at each step is exactly what prevents us from over-counting — each time, the entire previous contribution from INLINECODE148 is subsumed into the fresh, larger count.

14. Optimized Code

CODEBLOCK4

CODEBLOCK5

15. Explain Optimized Code Line by Line

INLINECODE149 — the modulus specified by the problem; we'll apply INLINECODE150 throughout to keep numbers bounded. INLINECODE151 — our 26-letter tracker: INLINECODE152 will always represent "the current count of distinct subsequences that end with letter INLINECODE153," using everything processed so far. INLINECODE154 — the running grand total of all distinct non-empty subsequences so far (equivalently, INLINECODE155, but we maintain it incrementally rather than re-summing every time, for efficiency). The INLINECODE156 loop — processes each character of INLINECODE157, left to right, exactly once. INLINECODE158 — converts the character to its 0-25 array index. INLINECODE159 — this is the heart of the insight from Section 12: the fresh count of "distinct subsequences ending in INLINECODE160," accounting for both "INLINECODE161 alone" (the INLINECODE162) and "every previously-existing distinct subsequence, with INLINECODE163 now appended" (the INLINECODE164 term, since appending the same final character to all of them keeps them pairwise distinct from each other, as their "everything before this last character" parts were already all different). INLINECODE165 — this line carefully updates the grand total: we remove this letter's old contribution (INLINECODE166, whatever it was before, possibly INLINECODE167 if this is INLINECODE168's first appearance) and add in its brand-new contribution (INLINECODE169). The extra INLINECODE170 before the final INLINECODE171 is a standard safety trick in modular arithmetic to prevent the intermediate value from accidentally going negative (since Java's INLINECODE172 on a negative number can return a negative result, and subtracting INLINECODE173 could momentarily make the running expression dip below zero before the mod wraps it back around correctly). INLINECODE174 — finally, we overwrite (not add to!) this letter's tracked count with the fresh value — reflecting that any older subsequences ending in this letter are now effectively superseded by this newer, larger count. After the loop finishes, INLINECODE175 holds the exact answer: the count of all distinct non-empty subsequences, already reduced modulo INLINECODE176.

16. Test With Multiple Examples

Example 1 — Normal Case

INLINECODE177 (all distinct characters, no repeats): Process INLINECODE178: INLINECODE179. INLINECODE180. INLINECODE181. Process INLINECODE182: INLINECODE183. INLINECODE184. INLINECODE185. Process INLINECODE186: INLINECODE187. INLINECODE188. INLINECODE189. Output: INLINECODE190 ✔️ (matches: INLINECODE191 — exactly 7)

Example 2 — Different Case

INLINECODE192 → dry-ran conceptually in Sections 6 and matches the mechanics shown in Section 13 for INLINECODE193 (just with a INLINECODE194 in between) → Output: INLINECODE195 ✔️

Example 3 — Edge Case

INLINECODE196 → dry-ran fully in Section 13 → Output: INLINECODE197 ✔️

17. Edge Cases

Single character (INLINECODE198 has length 1) → INLINECODE199, INLINECODE200 → correctly returns INLINECODE201 (the one-character string itself is the only distinct non-empty subsequence). All characters identical (like INLINECODE202 or longer runs) → as shown, the count grows linearly-ish in a specific pattern (INLINECODE203 for the running INLINECODE204 value of that one letter, since INLINECODE205 always equals INLINECODE206 when only one letter has ever appeared) — specifically, for a run of INLINECODE207 identical characters, the distinct subsequence count is exactly INLINECODE208 (just "the letter repeated 1 time," "repeated 2 times," ..., "repeated k times"). All characters distinct (like INLINECODE209) → the count grows like INLINECODE210 (every non-empty subset of positions gives a genuinely distinct string, since there's no way to confuse which letters were used) — our formula naturally produces this, since INLINECODE211 roughly doubles (plus 1) with each brand-new letter. Very long strings (INLINECODE212 up to 2000) with many repeated letters scattered throughout → handled correctly and efficiently, since the "replace, don't add" rule for INLINECODE213 correctly accounts for however many times each letter has reappeared, no matter the pattern. Modulo wraparound — since INLINECODE214 can be up to length 2000, and distinct-subsequence counts can grow roughly exponentially before the modulus "kicks in" conceptually, correctly applying INLINECODE215 (including the INLINECODE216 safety pad before subtracting) at every step is essential to avoid incorrect negative or overflowed intermediate values.

18. Time Complexity

What is time complexity? An estimate of how much work grows as the input grows, using a general scaling trend.

CODEBLOCK6

Why: Our optimized solution touches each character of INLINECODE217 exactly once, and for each character does only a small, fixed amount of work (one array lookup, a couple of additions/subtractions, one array write) — completely independent of how large the distinct-subsequence count actually is. For INLINECODE218, that's a trivial 2000 iterations, regardless of whether the "true" distinct count is small or astronomically large — we never need to touch that magnitude of work directly, since we're only ever manipulating a handful of numbers.

19. Space Complexity

INLINECODE219 — a small, fixed-size array, regardless of how long INLINECODE220 is. A couple of extra INLINECODE221 variables (INLINECODE222, INLINECODE223, INLINECODE224).

Extra space: INLINECODE225 (technically INLINECODE226 for the array, which is a constant, not something that grows with INLINECODE227).

20. Common Mistakes Beginners Make

❌ "I should literally generate and store every subsequence string, then deduplicate with a Set." ✅ This is exponentially too slow/memory-heavy for INLINECODE228 up to length 2000 — you must track only counts, per ending letter, never actual strings. ❌ "When I see a repeated letter, I should just ADD its new contribution to the old INLINECODE229 value." ✅ This causes over-counting — the correct move is to replace INLINECODE230 entirely with the newly computed value, since the new value already properly accounts for everything that came before (including previous appearances of that same letter), making the old value redundant to add on top of. ❌ "I don't need to worry about negative numbers in modular arithmetic." ✅ In Java, INLINECODE231 can return a negative result when applied to a negative number (e.g., INLINECODE232 in Java, not INLINECODE233 like in some other languages/math conventions) — so when subtracting INLINECODE234 from INLINECODE235, you should add INLINECODE236 back before the final INLINECODE237 to guarantee a non-negative result. ❌ "The INLINECODE238 in INLINECODE239 is unnecessary — appending the character to existing subsequences should be enough." ✅ The INLINECODE240 specifically accounts for "this character all by itself" as a brand-new one-character subsequence — without it, you'd never count single-character subsequences correctly the first time each letter appears (or undercount them thereafter). ❌ "I need to take the modulus only at the very end, once, on the final total." ✅ Because the "true" unbounded numbers can grow far beyond what fits in a normal integer during the computation (not just at the end), you must apply INLINECODE241 at every intermediate step, not just once at the very end — otherwise you'd get integer overflow long before reaching the final answer.

21. How to Recognize This Pattern in Other Problems

Watch for these signal phrases:

CODEBLOCK7

Whenever a problem wants you to count distinct results built by extending a structure one element at a time, and duplicates come from repeated values in a small alphabet, think: track a per-value running count ("subsequences/sequences ending in this specific value"), and REPLACE (don't add to) that value's count whenever it reoccurs — this is the standard trick for turning an "exponentially many distinct results" problem into an O(n)-time counting problem.

22. Interview Thinking

CODEBLOCK8

Applied here: the interview-winning realization is that "distinct" + "small alphabet" should immediately suggest tracking per-character running totals with a replace rule, rather than ever trying to materialize or deduplicate actual strings.

23. Mini Challenge

Try these before checking the answers:

1. Why does appending the same new character INLINECODE242 to every currently-distinct subsequence always produce a set of results that are still pairwise distinct from each other (never colliding with one another)? 2. If INLINECODE243 and later in the string another INLINECODE244 appears when INLINECODE245, what does the new INLINECODE246 become, and what happens to the old value INLINECODE247? 3. Why is it safe to completely discard/replace the old INLINECODE248 value, rather than needing to somehow "merge" it with the new one?

Answer to Mini Challenge

1. Because right before appending INLINECODE249, all the existing subsequences being extended were already guaranteed pairwise distinct from each other (that's what INLINECODE250 represents — a count of genuinely different strings). Tacking the identical final character INLINECODE251 onto each of them can't possibly make two previously-different strings become equal — if two strings differed anywhere in their content before, they still differ there after both get the same suffix appended. 2. New INLINECODE252. The old value INLINECODE253 is discarded/overwritten — it's not used in computing the new value directly (except insofar as it had already been folded into INLINECODE254 long ago when it was first established), and it's specifically subtracted back out of INLINECODE255 before adding in the new INLINECODE256, to avoid double-counting. 3. Because the new value INLINECODE257 already represents "every distinct subsequence ending in INLINECODE258, using everything processed up through this point" — which is a strictly more complete and up-to-date accounting than the old value (which only reflected an earlier, smaller prefix of INLINECODE259). The old subsequences ending in the previous INLINECODE260 are not lost — they're representable as ways to reach the same final strings, but since we only care about distinct string counts (not "ways"), there's no need to preserve or merge the old number at all.

24. Final Revision

🧠 Problem in One Sentence
Count the number of distinct non-empty subsequence strings of INLINECODE261, modulo INLINECODE262.
🔑 Main Idea
Track, per letter, how many distinct subsequences currently end in that letter; each new character's fresh count is INLINECODE263, and this fresh count REPLACES (not adds to) that letter's previous count, correctly avoiding duplicate counting from repeated letters.
⚙️ Algorithm
1. Maintain INLINECODE264 (per-letter counts) and INLINECODE265 (their sum), all starting at 0. 2. For each character INLINECODE266 in INLINECODE267: compute INLINECODE268. 3. Update INLINECODE269. 4. Set INLINECODE270. 5. Return INLINECODE271 after processing all characters.
⏱️ Complexity
Time: INLINECODE272 Space: INLINECODE273 (a fixed 26-element array)
🎯 Pattern to Remember
"Count distinct results, mod a big prime, built from a small alphabet" → track per-value running counts, and REPLACE (not add) a value's count whenever it reoccurs, rather than trying to enumerate or deduplicate actual results.

25. Beginner Quiz

1. (Understanding) Why can't we just count subsequences the way problem #115 did (counting ways*) and expect that to equal the answer here? 2. (Basic concept) What does INLINECODE274 represent, in plain words, at any point during the algorithm? 3. (Logic) Why do we REPLACE INLINECODE275 with the new value instead of adding the new value on top of the old one? 4. (Dry run) For INLINECODE276, walk through the algorithm step by step (tracking INLINECODE277, INLINECODE278, and INLINECODE279) and find the final answer. 5. (Complexity/pattern) Why would literally storing every distinct subsequence in a INLINECODE280 be infeasible for INLINECODE281 of length 2000, and what specific property of the problem (small alphabet + "distinct" + modulo output) should immediately suggest the per-letter running-count technique?