1987. Number of Unique Good Subsequences [Python]
\n\npython\nclass Solution:\n    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n        mod = 10**9 + 7\n        dp = [[0, 0] for _ in range(2)]
\n\n```python\nclass Solution:\n    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n        mod = 10**9 + 7\n        dp = [[0, 0] for _ in range(2)]  # dp[i][j] represents count of subsequences ending at index i with last element j (0 or 1)\n        n = len(binary)\n        \n        for ch in binary:\n            if ch == \'0\':\n                # For a \'0\', we have two cases:\n                # 1. Extend the subsequences ending with \'0\' by one more \'0\'.\n                # 2. Extend the subsequences ending with \'1\' by appending this \'0\' to form new subsequences.\n                dp[0][0] = 1\n                dp[1][0] = (dp[1][0] + dp[1][1]) % mod\n            else:\n                # For a \'1\', we have one case:\n                # Extend the subsequences ending with \'0\' or \'1\' by appending this \'1\' to form new subsequences.\n                dp[1][1] = (dp[1][0] + dp[1][1] + 1) % mod\n        \n        # The answer is the sum of counts of subsequences ending with \'0\' and \'1\',\n        # considering all the possibilities.\n        result = (dp[0][0] + dp[0][1] + dp[1][0] + dp[1][1]) % mod\n        return result\n\n# Create an instance of the Solution class\nsol = Solution()\n\n# Test cases\nprint(sol.numberOfUniqueGoodSubsequences("001"))  # Output: 2\nprint(sol.numberOfUniqueGoodSubsequences("11"))   # Output: 2\nprint(sol.numberOfUniqueGoodSubsequences("101"))  # Output: 5\n```\n\n**Intuition:**\n\nThe algorithm works by maintaining two sets of counts for each index: `dp[i][0]` represents the count of subsequences ending at index `i` with the last element being \'0\', and `dp[i][1]` represents the count of subsequences ending at index `i` with the last element being \'1\'. \n\nWhen a \'0\' is encountered, two possibilities arise:\n1. We can extend the subsequences ending with \'0\' by one more \'0\', and this count is updated in `dp[0][0]`.\n2. We can append this \'0\' to subsequences ending with \'1\', creating new subsequences, and this count is updated in `dp[1][0]`.\n\nWhen a \'1\' is encountered, we can extend the subsequences ending with \'0\' or \'1\' by appending this \'1\' to form new subsequences. This count is updated in `dp[1][1]`.\n\nFinally, the answer is the sum of counts of subsequences ending with \'0\' and \'1\', considering all the possibilities.\n\n**Time Complexity:**\n\nThe algorithm iterates through the binary string once, performing constant time operations for each character. Hence, the time complexity is O(N), where N is the length of the binary string. The space complexity is O(1) since we are using a fixed-size array for dynamic programming.\n\n# Code\n```\nclass Solution:\n    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n        mod = 10**9 + 7\n        dp = [[0, 0] for _ in range(2)]\n        n = len(binary)\n        \n        for ch in binary:\n            if ch == \'0\':\n                dp[0][0] = 1\n                dp[1][0] = (dp[1][0] + dp[1][1]) % mod\n            else:\n                dp[1][1] = (dp[1][0] + dp[1][1] + 1) % mod\n        \n        return (dp[0][0] + dp[0][1] + dp[1][0] + dp[1][1]) % mod\n```
['Python3']