Abstract / Summary

Count all unique subsequences of a given string that start with one character and end with a different character.

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).

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 routine computes the number of distinct “good” subsequences that can be formed from a binary string. A good subsequence is defined as a non-empty subsequence that does not contain leading zeros, except for the subsequence consisting of a single zero. The result is returned modulo 1 000 000 007.

Core Logic

Four integer variables drive the computation:

modulo = 1_000_000_007
zero = 0          # counts good subsequences that end with '0'
one  = 0          # counts good subsequences that end with '1'
both = 0          # total of zero and one
null = 0          # becomes 1 once a '0' appears, representing the single-character subsequence "0"

zero and one keep separate tallies for subsequences whose last character is respectively ‘0’ or ‘1’. both is always the sum of those two counts, and null records whether the trivial subsequence “0” is available.

Iteration Over Characters

The algorithm scans the input string once, updating the counters based on the current character.

for c in binary:
    if c == "0":
        zero = both
        null = 1
    else:
        one = both + 1
    both = (zero + one) % modulo

When a ‘0’ is encountered, every existing good subsequence (whether ending in ‘0’ or ‘1’) can be extended by this ‘0’, producing new subsequences that now end in ‘0’. Hence zero receives the previous total both. The flag null is set to 1 because the single-character subsequence “0” becomes valid at this point.

When a ‘1’ is encountered, it can be appended to any existing good subsequence, and additionally it can start a new subsequence consisting solely of ‘1’. Therefore one becomes both + 1. The extra +1 accounts for the brand-new subsequence “1”.

After handling the character, both is recomputed as the sum of the updated zero and one, reduced modulo the large prime to keep the numbers bounded.

Final Result

When the loop finishes, the answer consists of all good subsequences that end with either digit (both) plus the solitary “0” subsequence if it ever appeared (null). The modulo operation is applied once more before returning.

return (both + null) % modulo

Edge Cases Handled

If the input string is empty, the loop body never executes; both and null remain zero, and the function correctly returns zero because no non-empty subsequence exists.

When the string contains only zeros, each new zero copies the current total of good subsequences into zero. Since no ‘1’ ever appears, one stays zero, and both mirrors zero. The flag null becomes 1 on the first zero, ensuring the single-character “0” is counted exactly once regardless of how many zeros follow.

If the string consists solely of ones, zero never changes from zero, while one grows by adding the current total plus one for each new ‘1’. This correctly enumerates all distinct subsequences that end with ‘1’, including the solitary “1”.

Strings that start with zeros are also covered: the first zero sets null to 1, but because good subsequences cannot have leading zeros, the algorithm never treats a leading zero as the start of a longer subsequence; it only propagates existing subsequences (which are initially none) and records the isolated “0”. Subsequent characters follow the same rules, guaranteeing that only valid subsequences are counted.

Performance Optimizations

The implementation runs in a single pass over the input, achieving linear time relative to the length of the binary string. Only four integer variables are maintained, giving constant auxiliary space regardless of input size.

Modulo reduction is performed at each iteration when updating both, preventing integer overflow and keeping arithmetic operations cheap. The use of simple assignment statements avoids the overhead of more complex data structures such as sets or dictionaries, which would otherwise be required to track distinct subsequences explicitly. This lean approach yields fast execution even for very long strings.

Imagine you have a long row of building blocks with some being blue and others being red. This code is helping you count all the special patterns you can build using those blocks.

The computer keeps track of two treasure chests. One chest holds patterns that end with a red block, and the other chest holds patterns that end with a blue block. Every time the computer looks at a new block in the row, it decides which chest to add it to. If it sees a blue block, it tries to attach that blue block to every pattern it has already made. It also counts the blue block by itself as a brand new pattern. If it sees a red block, it attaches that red block to all the patterns in the other chests too.

Because there could be a very huge number of patterns, the code keeps them in a smaller bucket to make sure the number stays easy to manage. It also keeps a tiny extra note to remember if it ever found a red block so it can include that at the very end. By looking at all the blocks one by one and moving them into these chests, the computer can figure out exactly how many unique patterns can be made.

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
	muhammadfarhankt					Go
	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
muhammadfarhankt	Go
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