LeetCode-in-Java
1987. Number of Unique Good Subsequences
Hard
You are given a binary string binary. A subsequence of binary is considered good if it is not empty and has no leading zeros (with the exception of "0").
Find the number of unique good subsequences of binary.
- For example, if
binary = "001", then all the good subsequences are["0", "0", "1"], so the unique good subsequences are"0"and"1". Note that subsequences"00","01", and"001"are not good because they have leading zeros.
Return the number of unique good subsequences of binary. Since the answer may be very large, return it modulo 109 + 7.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: binary = “001”
Output: 2
Explanation: The good subsequences of binary are [“0”, “0”, “1”].
The unique good subsequences are “0” and “1”.
Example 2:
Input: binary = “11”
Output: 2
Explanation: The good subsequences of binary are [“1”, “1”, “11”].
The unique good subsequences are “1” and “11”.
Example 3:
Input: binary = “101”
Output: 5
Explanation: The good subsequences of binary are [“1”, “0”, “1”, “10”, “11”, “101”].
The unique good subsequences are “0”, “1”, “10”, “11”, and “101”.
Constraints:
1 <= binary.length <= 105binaryconsists of only'0's and'1's.
Solution
public class Solution {
private static final int MOD = 1000000007;
public int numberOfUniqueGoodSubsequences(String binary) {
boolean addZero = false;
// in the first round we "concat" to the empty binary
int count = 1;
int[] countEndsWith = new int[2];
for (int i = 0; i < binary.length(); i++) {
char c = binary.charAt(i);
int cIndex = c - '0';
// all valid sub-binaries + c at the end => same count
int endsWithCCount = count;
if (c == '0') {
addZero = true;
// every time c is '0', we concat it to "" and get "0" - we wish to count it only
// once (done in the end)
endsWithCCount--;
}
// w/out c at the end minus dups (= already end with c)
count = (count + endsWithCCount - countEndsWith[cIndex]) % MOD;
// may be negative due to MOD
count = count < 0 ? count + MOD : count;
countEndsWith[cIndex] = endsWithCCount;
}
// remove the empty binary
count--;
// add "0"
if (addZero) {
count++;
}
return count;
}
}