Number of Unique Good Subsequences LeetCode solution in Python

1
class Solution:
2
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
3

4
        # zero_as_last: the count of S0, good sequence ending in 0
5
        # one_as_last : the count of S1: good sequence ending in 1
6
        # zero_exist:   existence flag of 0 in given binary
7

8
        dp = {"zero_as_last": 0, "one_as_last": 0, "zero_exist": 0}
9

10
        for bit in map(int, binary):
11

12
            if bit:
13
                # current good = ( S0 concate with 1 ) + ( S1 concate with 1 ) + 1 alone
14
                # + "1" is allowed because leading 1 is valid by description
15
                dp["one_as_last"] = dp["zero_as_last"] + dp["one_as_last"] + 1
16

17
            else:
18
                # current good = ( S0 concate with 0 ) + ( S1 concate with 0 )
19
                # + "0" is NOT allowed because leading 0 is invalid by description
20
                dp["zero_as_last"] = dp["zero_as_last"] + dp["one_as_last"]
21

22
            # check the existence of 0
23
            dp["zero_exist"] |= 1 - bit
24

25
        return sum(dp.values()) % (10**9 + 7)