C++ || DP || O(N)/O(1) || Simple || Notes
\n// Check if any Zero\n// Find the first 1, start count after the first 1 (The first 1 will be in all the combination other than "0")\n// for every digit multi
```\n// Check if any Zero\n// Find the first 1, start count after the first 1 (The first 1 will be in all the combination other than "0")\n// for every digit multiple the number - duplications\n// Duplication - In the case where we remove all the character between identical characters\n//                        The remove of either produce identical string.\n//                        Example:   "1010---0"  => "101----0" identical to "1010----"\n//                        In this case we have to dedact the count of "1010" (the combinations of "101")\n// add 1 if any 0 for the single "0" case\nclass Solution {\npublic:\n    int numberOfUniqueGoodSubsequences(string binary) {\n        int n = binary.length();\n        bool any_zero = (binary.find(\'0\') < n); \n        long long count = 0;\n        int zeros = 0;\n        int ones  = 0;\n        int i = 0;\n\t\t// Search the first \'1\' - The first \'1\' will be part of all the combination other than single \'0\'\n        for (; i<n; i++)\n        {\n            if (binary[i] == \'1\')\n            {\n\t\t\t   // count the first \'1\'\n                count++;\n                i++; \n                break;\n            }\n        }\n       // After the first \'1\' treat \'1\' and \'0\' the same way\n        for (; i<n; i++)\n        {\n            char c = binary[i];\n            int prev = count;\n            if (c == \'0\')\n            {\n                count = (count*2-zeros) %1000000007;\n                zeros = prev;\n            }\n            else\n            {\n                count = (count*2-ones) %1000000007;\n                ones = prev;\n            }\n            if (count < 0) count += 1000000007;\n        }\n\t\t// add the case of single \'0\'\n        if (any_zero)\n            count = (count+1) %1000000007;\n\n        return count;\n  \n    }\n};\n```
[]