Number of Unique Good Subsequences — Problem & Solution
Number of Unique Good Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Number of Unique Good Subsequences is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a binary string binary. A subsequence of binary is good if it is non-empty and has no leading zeros — the only good subsequence that starts with 0 is "0" itself.
Return the number of distinct good subsequences of binary, counted as strings (equal strings obtained from different positions count once), modulo 10^9 + 7.
Example 1
Input: binary = "001"
Output: 2
Explanation: The good subsequences are `"0"`, `"0"` and `"1"`; as strings that is `"0"` and `"1"`.
Example 2
Input: binary = "110"
Output: 5
Explanation: `"0"`, `"1"`, `"10"`, `"11"` and `"110"`.
Example 3
Input: binary = "1011"
Output: 7
Constraints
1 <= binary.length <= 10^5binary consists of only '0's and '1's
Hints for Number of Unique Good Subsequences
Hint 1
Set
"0"aside — it is good exactly when the string contains a 0. Every other good subsequence starts with1.Hint 2
Count distinct subsequences that start with
1, split by their last character:end0andend1.Hint 3
Reading a
1: every distinct one (ending in 0 or 1) can be extended by it, and"1"itself appears —end1 = end0 + end1 + 1. Reading a0:end0 = end0 + end1. The answer isend0 + end1 + (1 if any 0).
How to solve Number of Unique Good Subsequences
Count distinct strings by their last character. After reading a prefix, let end0 (end1) be the number of distinct subsequences that start with 1 and end with 0 (1). Appending the next character c to every distinct subsequence produces every distinct subsequence ending in c — the new set already contains all the old ones ending in c, so there is no double counting.
Approach
- Start with
end0 = end1 = 0andhasZero = 0. - For each character: on
1, setend1 = end0 + end1 + 1(extend everything, plus the string"1"); on0, setend0 = end0 + end1andhasZero = 1(a 0 cannot start a good subsequence other than"0"). - Reduce modulo 10^9 + 7 at each step.
- Return
end0 + end1 + hasZeromodulo 10^9 + 7.
Why it works
Fix a prefix and a string t that starts with 1 and ends with c. If t is a subsequence of the prefix, it can be matched greedily so that its last character uses the latest c; removing that character leaves a distinct subsequence of the earlier part (or the empty string, when t = "1"). So the distinct strings ending in c after reading this c are exactly the previous distinct strings with c appended, plus "1" when c = 1 — which is the update. Strings ending in the other character are unchanged.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
"0"counts once if any 0 exists — it is not built by the recurrence.- A 0 never starts a counted subsequence, so the 0-update has no
+ 1. - Counting by positions instead of by strings overcounts heavily (
"11"has three subsequences but two distinct strings).
Reference solution
Python
def numberOfUniqueGoodSubsequences(binary: str) -> int:
MOD = 10 ** 9 + 7
end0 = end1 = 0
has_zero = 0
for ch in binary:
if ch == '1':
end1 = (end0 + end1 + 1) % MOD
else:
end0 = (end0 + end1) % MOD
has_zero = 1
return (end0 + end1 + has_zero) % MODJava
public static int numberOfUniqueGoodSubsequences(String binary) {
final long MOD = 1000000007L;
long end0 = 0, end1 = 0, hasZero = 0;
for (int i = 0; i < binary.length(); i++) {
if (binary.charAt(i) == '1') end1 = (end0 + end1 + 1) % MOD;
else {
end0 = (end0 + end1) % MOD;
hasZero = 1;
}
}
return (int) ((end0 + end1 + hasZero) % MOD);
}C++
int numberOfUniqueGoodSubsequences(string binary) {
const long long MOD = 1000000007LL;
long long end0 = 0, end1 = 0, hasZero = 0;
for (char ch : binary) {
if (ch == '1') end1 = (end0 + end1 + 1) % MOD;
else {
end0 = (end0 + end1) % MOD;
hasZero = 1;
}
}
return (int)((end0 + end1 + hasZero) % MOD);
}JavaScript
var numberOfUniqueGoodSubsequences = function(binary) {
var MOD = 1000000007, end0 = 0, end1 = 0, hasZero = 0;
for (var i = 0; i < binary.length; i++) {
if (binary[i] === '1') end1 = (end0 + end1 + 1) % MOD;
else {
end0 = (end0 + end1) % MOD;
hasZero = 1;
}
}
return (end0 + end1 + hasZero) % MOD;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming