DP approach and similar question
I know there are other solutions that involve O(1) space and O(n) time. I anyways will post my DP solution. The idea is inspired from https://leetcode.com/probl
I know there are other solutions that involve O(1) space and O(n) time. I anyways will post my DP solution. The idea is inspired from https://leetcode.com/problems/number-of-unique-good-subsequences/\ncount distinct subsequences problem on leetcode itself. Here is well commented code:\n\n```\nclass Solution {\npublic:\n    int mod = 1e9 + 7;\n    int numberOfUniqueGoodSubsequences(string str) {\n        int n = str.size();\n        // dp0[i] represents number of subsequences starting with 0 from index i\n        // dp1[i] represents number of subsequences starting with 1 from index i\n        vector<long> dp0(n + 1), dp1(n + 1);\n        int i, c = 0;\n        // M stores the last occurence of character (in our case it can be either 0 or 1)\n        map<char, int> M;\n        \n        // rest of the transition is same as problem: count number of distinct subsequences.\n        for(i = n - 1; i >= 0; --i) {\n            if(str[i] == \'0\') {\n                c = 1;\n                dp0[i] = dp1[i + 1] + 2 * dp0[i + 1] + 1;\n                if(M.count(str[i])) {\n                    dp0[i] -= (dp0[M[str[i]] + 1] + dp1[M[str[i]] + 1] + 1);\n                }\n                dp1[i] = dp1[i + 1];\n                dp0[i] += mod;\n                dp0[i] %= mod;\n            } else {\n                dp1[i] = 2 * dp1[i + 1] + dp0[i + 1] + 1;\n                if(M.count(str[i])) {\n                    dp1[i] -= (dp0[M[str[i]] + 1] + dp1[M[str[i]] + 1] + 1);\n                }\n                dp0[i] = dp0[i + 1];\n                dp1[i] += mod;\n                dp1[i] %= mod;\n            }\n            M[str[i]] = i;\n        }\n        for(int i = 0; i < n; ++i) {\n            if(str[i] == \'1\') {\n                return dp1[i] + c;\n            }\n        }\n        return c;\n        \n    }\n};\n```
[]