Abstract / Summary

Count the number of subsequences in a given string that are equal to a specified word.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 53% (30k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method countSpecialSubsequences that computes the number of subsequences in a list nums that follow the exact pattern 0 → 1 → 2, possibly with repetitions of each value, and returns the result modulo 1 000 000 007. The algorithm processes the input in a single pass, maintaining three counters that represent the number of valid partial subsequences ending with each of the three required values. By updating these counters according to the current element, the method accumulates the total count of complete 0-1-2 subsequences without enumerating any subsequence explicitly.

Core Logic

Initialization

modulo = 1_000_000_007
zero = 0
one  = 0
two  = 0

Three integer variables are created: zero tracks subsequences that consist solely of zeros, one tracks subsequences that have progressed to the 0-1 stage, and two tracks fully formed 0-1-2 subsequences. The modulo constant is stored for later reduction.

Iteration Over Input

for i, n in enumerate(nums):
    if   n == 0:
        zero += zero + 1
    elif n == 1:
        one  += one  + zero
    elif n == 2:
        two  += two  + one

During each iteration the algorithm distinguishes the current value n.

• When n equals 0, every existing zero-ending subsequence can be extended by appending the new zero, and a new subsequence consisting of the single element also starts. Hence zero is increased by zero + 1.

• When n equals 1, each existing one-ending subsequence can be extended, and each zero-ending subsequence can transition to the 0-1 stage by appending the current 1. The update one += one + zero captures both possibilities.

• When n equals 2, the same pattern applies: existing two-ending subsequences are extended, and each one-ending subsequence can be completed into a full 0-1-2 subsequence. The statement two += two + one reflects this.

Values other than 0, 1, 2 are ignored, leaving the counters unchanged for those positions.

Periodic Modulo Reduction

if (i & 15) == 0:
    zero %= modulo
    one  %= modulo
    two  %= modulo

To keep the intermediate counters within the range of a 64-bit integer and to avoid overflow, the algorithm reduces each counter modulo modulo at regular intervals. The condition (i & 15) == 0 triggers the reduction every 16 iterations, using a bitwise AND to test the low four bits of the index. This approach balances the cost of the modulo operation against the risk of integer overflow.

Final Result

return two % modulo

After processing the entire list, the method returns the count of complete 0-1-2 subsequences, applying the modulo one final time to guarantee the result conforms to the required range.

Edge Cases Handled

When the input list is empty, the loop body never executes, leaving all counters at zero. The final modulo operation therefore returns zero, correctly indicating that no special subsequence exists.

If the list contains only zeros, the zero counter grows according to the recurrence zero = zero * 2 + 1. The algorithm correctly counts every non-empty subset of zeros as a valid zero-only subsequence, while one and two remain zero, resulting in a final answer of zero.

When the list contains only ones or only twos, the corresponding updates never fire because the prerequisite counters (zero for ones, one for twos) stay at zero. Consequently, the final result is zero, reflecting the impossibility of forming a complete 0-1-2 pattern without the preceding values.

Mixed inputs where the required order is violated (for example, a 2 appearing before any 1) are also handled gracefully: the two counter only increases when a preceding one subsequence exists, so stray 2s do not contribute to the final count.

Performance Optimizations

The algorithm achieves linear time performance by avoiding nested loops or explicit subsequence generation. Each element is examined once, and the state updates consist of a few integer additions.

The use of three scalar variables instead of larger data structures minimizes memory footprint and improves cache locality.

Periodic modulo reduction, triggered by a bitwise check, reduces the frequency of the relatively expensive % operation. By performing the reduction every 16 steps, the code limits the growth of the counters while keeping the overhead low. The bitwise condition (i & 15) == 0 is faster than a modulo test because it translates to a single CPU instruction.

All arithmetic operations are performed with native Python integers, which are automatically promoted to arbitrary-precision when needed. The occasional modulo ensures that the numbers stay within a manageable size, preventing the interpreter from allocating excessively large objects and thereby preserving execution speed.

Imagine there is a magical garden party where people can only stand in line in a very specific order. Everyone must arrive as a zero, then a one, and finally a two. Some friends might decide to join the line based on who is already standing there.

Think of the three buckets labeled zero, one, and two. These buckets keep track of how many different groups of friends are currently waiting in the line.

When a person who is a zero arrives, they can start a brand new group all by themselves, or they can join the end of any group that is already made up of only zeros. Because of this, the number of groups ending in zero doubles, plus there is that one new group the person just started.

When a person who is a one arrives, they look at all the groups that are currently just zeros. They jump onto the back of those groups to turn them into zero-one sequences. They also join any groups that already have ones in them, so the number of one-groups grows by adding itself plus the number of zero-groups.

When a person who is a two arrives, they can only join groups that have already finished their zero-one stage. Just like before, they help the existing number of two-groups grow by adding the number of groups that were already ending in one.

The big number mentioned at the start is just a rule to make sure the counts stay small enough for the computer to handle easily, sort of like resetting a counter once it gets too high. By the time every person has walked through the garden, the bucket for the twos tells the total number of perfectly ordered groups that were formed.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java			TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java		Go	TS
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality