Number of Unique Good Subsequences
01 · Problem
You are given a binary string binary (only characters '0' and '1'). A subsequence of binary is good if it is non-empty and has no leading zeros. The single-character string "0" is the only good subsequence allowed to start with '0'.
Return the number of distinct good subsequences of binary. Subsequences are compared as strings, so the same string produced from different index choices is counted only once. Return the answer modulo 10^9 + 7.
For example, in "001" the strings "0" and "1" are good, while "00", "01" and "001" are not because they start with a zero.
02 · Examples
binary = "001"
2
The distinct non-empty subsequences are "0", "1", "00", "01" and "001". Only "0" and "1" have no leading zero ("0" itself is allowed).
binary = "11"
2
The distinct good subsequences are "1" and "11".
binary = "101"
5
The distinct good subsequences are "0", "1", "10", "11" and "101".
03 · Constraints
- 011 <= binary.length <= 105
- 02binary[i] is either '0' or '1'
- 03Return the answer modulo 109 + 7
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.