Dynamic Programming Solution - End with 0/1
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind this solution is to use dynamic programming to count the number of
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind this solution is to use dynamic programming to count the number of unique good subsequences. We can keep track of subsequences ending with \'0\' and \'1\' separately, and build longer subsequences from shorter ones.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. We use a vector `dp` of size 2 to store the count of good subsequences:\n   - `dp[0]` represents the count of good subsequences ending with \'0\'\n   - `dp[1]` represents the count of good subsequences ending with \'1\'\n\n2. We iterate through the binary string:\n   - For \'0\', we update `dp[0]` by adding `dp[1]` to it (all good subsequences ending with \'1\' can now end with \'0\')\n   - For \'1\', we update `dp[1]` by adding `dp[0]`, `dp[1]`, and 1 (all existing good subsequences plus the new subsequence \'1\')\n\n3. We use a boolean `has_zero` to keep track of whether we\'ve seen a \'0\' in the string.\n\n4. At the end, we return the sum of `dp[0]`, `dp[1]`, and `has_zero` (to account for the "0" subsequence if it exists).\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe algorithm iterates through the input string once, performing constant-time operations for each character.\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nWe use a fixed-size vector `dp` of size 2 and a boolean variable, which is constant extra space regardless of the input size.\n\n# Code\n```\nclass Solution {\npublic:\n    int numberOfUniqueGoodSubsequences(string binary) {\n        const int MOD = 1000000007;\n        int n = binary.length();\n        vector<long long> dp(2, 0);\n        bool haszero = false;\n        \n        for (char c : binary) {\n            if (c == \'0\') {\n                haszero = true;\n                dp[0] = (dp[0] + dp[1]) % MOD;\n            } else {\n                dp[1] = (dp[0] + dp[1] + 1) % MOD;\n            }\n        }\n        \n        return (dp[0] + dp[1] + haszero) % MOD;\n    }\n};\n```
['C++']