[C++] Explained O(n) time, O(1) space DP
Lets use 2 set to represent strings that are awaiting 1 and 0 to create a sub sequence respectively, let\'s call them exp1 and exp0. We also define a variable t
Lets use 2 set to represent strings that are awaiting 1 and 0 to create a sub sequence respectively, let\'s call them exp1 and exp0. We also define a variable to check if there is a zero in string as a special case handle, hence the variable (bool) hasZero. Let\'s run through an example "101":\n\nAt the beginning, we are expecting 1 to get our first sub sequence, thus:\nexp0: []\nexp1: [""]\nhasZero = false\nresult: []\n\nat i = 0, the character is \'1\', we add it to the expected 1 set, the incoming 1 has created unique subsequence equal to the size of exp1, so res += exp1.size(), and the new 1 will also be expecting a 0 to form a new subsequence:\nexp0: ["1"]\nexp1: ["1"]\nhasZero = false\nresult: ["1"]\n\nat i = 1, we repeat the previous logic, but use exp0 to replace exp1\nexp0: ["10"]\nexp1: ["1","10"]\nhasZero = true\nres = ["1", "10"]\n\nat i = 2:\nexp0: ["10","11","101"]\nexp1: ["11", "101"]\nhasZero = true;\nres = ["1","10","11","101"]\n\nbecause we have a zero as a unique sub-sequence, so add it to res\nres = ["0","1","10","11","101"]\nres.size() = 5\n\nWe can simply use a count as space optimization if you observe the pattern.\n\n```\nclass Solution {\nprivate:\n    const int M = 1e9 + 7;\npublic:\n    int numberOfUniqueGoodSubsequences(string binary) {\n        int res = 0;\n        bool hasZero = false;\n        int exp0 = 0;\n        int exp1 = 1;\n        \n        for (char &eachC : binary) {\n            if (eachC == \'1\') {\n                res = (res + exp1) % M;\n                exp0 = (exp0 + exp1) % M;\n            } else {\n                hasZero = true;\n                res = (res + exp0) % M;\n                exp1 = (exp1 + exp0) % M;\n            }\n        }\n        if (hasZero) res = (res + 1) % M;\n        return res;\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']