Python/Go O(n) by DP [w/ Hint]
Python O(n) by DP\n\nHint:\n\nDefine\nS0 = the number of good subsequence count ending in 0\nS1 = the number of good subsequence count ending in 1\nF0 = the exi
Python O(n) by DP\n\n**Hint**:\n\nDefine\n**S0** = the number of good subsequence count **ending in 0**\n**S1** = the number of good subsequence count **ending in 1**\n**F0** = the **existence flag of 0** in input binary string\n\nDP( i ) computes and return S0, S1, F0 for index i\n\n```\n## Base case :\nif i == -1:\n\t\n\t# Empty string has no good subsequence\n\treturn 0, 0, 0\n```\n\n```\n## General cases:\nif i != -1\n\t\n\tif cut_digit == 1:\n\t\t\n\t\t# current good = ( S0 concate with 1 ) + ( S1 concate with 1 ) + 1 alone\n\t\t# + "1" is allowed because leading 1 is valid by description\n\t\tS1 = S0 + S1 + 1\n\t\tS0 = S0\n\t\t\n\telse:\n\t\t# current good = ( S0 concate with 0 ) + ( S1 concate with 0 ) \n\t\t# + "0" is NOT allowed because leading 0 is invalid by description\n\t\tS0 = S0 + S1\n\t\tS1 = S1\n\t\t\n\t\t# update existence flag of 0\n\t\tF0 = F0 | (1-cur_digit)\n\t\n\treturn S0, S1, F0\n```\n\n---\n\nFinal answer = **S0 + S1 + F0**\n( F0 is for **single "0"** if "0" exists in input binary string )\n\n---\n\n**Implementation** by bottom-up DP in Python:\n\n```\nclass Solution:\n    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n        \n        \n        # zero_as_last: the count of S0, good sequence ending in 0\n        # one_as_last : the count of S1: good sequence ending in 1\n        # zero_exist:   existence flag of 0 in given binary\n        \n        dp = {"zero_as_last": 0, "one_as_last": 0, "zero_exist": 0}\n        \n        for bit in map(int, binary):\n            \n            if bit:\n                # current good = ( S0 concate with 1 ) + ( S1 concate with 1 ) + 1 alone\n                # + "1" is allowed because leading 1 is valid by description\n                dp["one_as_last"] = dp["zero_as_last"] + dp["one_as_last"] + 1\n            \n            else:\n                # current good = ( S0 concate with 0 ) + ( S1 concate with 0 ) \n                # + "0" is NOT allowed because leading 0 is invalid by description\n                dp["zero_as_last"] = dp["zero_as_last"] + dp["one_as_last"]\n            \n            # check the existence of 0\n            dp["zero_exist"] |= (1-bit)\n        \n        \n        return sum( dp.values() ) % ( 10**9 + 7 )\n```\n\n---\n\n**Implementaiton** by Bottom-up DP in Golang\n\n```\n\nfunc numberOfUniqueGoodSubsequences(binary string) int {\n    \n    // Modulo constant, required by description\n    const modulo_const int = 1e9 + 7\n    \n    zero_as_last := 0\n    one_as_last := 0\n    zero_exist := 0\n    \n    for _, bitChar := range binary{\n        \n        \n        if bitChar == \'1\'{\n            one_as_last = (zero_as_last + one_as_last + 1) % (modulo_const)\n        }else{\n            zero_as_last = (zero_as_last + one_as_last ) % (modulo_const)\n            zero_exist = 1\n        }\n        \n        \n    }\n    \n    return (zero_as_last + one_as_last + zero_exist) % (modulo_const)\n    \n}\n```\n\n---\n\n**Implementation** by Top-down DP\n\n```\nclass Solution:\n    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n        \n       \n        def dp(ending_idx):\n            \n            if ending_idx == -1:\n                \n                return 0, 0 ,0\n            \n            else:\n                prev_zero, prev_one, zero_exist = dp(ending_idx-1)\n                \n                cur_digit = int( binary[ending_idx] )\n                \n                if cur_digit == 1:\n                    zero_as_last = prev_zero\n                    one_as_last = ( (prev_zero + prev_one) + 1 ) % (10**9+7)\n                \n                else:\n                    zero_as_last = ( (prev_zero + prev_one) ) %  (10**9+7)\n                    one_as_last = prev_one\n                    \n                    zero_exist = zero_exist | (1-cur_digit) \n                \n                \n                return zero_as_last, one_as_last, zero_exist\n        \n        # -------------------------\n\n        return  sum( dp( len(binary)-1 ) ) % (10**9+7)\n```\n\n---\n\nRelated leetcode challenge:\n\n[Leetcode #940 Distinct Subsequence II](https://leetcode.com/problems/distinct-subsequences-ii/)
['Dynamic Programming', 'Python', 'Go']