C++ | O(N) | DP | Similar to Distinct Subsequences II
Please do upvote if found useful!!\n\nclass Solution {\npublic:\n    const int M = 1e9 + 7;\n    int numberOfUniqueGoodSubsequences(string s) {\n        int n=s
Please do upvote if found useful!!\n```\nclass Solution {\npublic:\n    const int M = 1e9 + 7;\n    int numberOfUniqueGoodSubsequences(string s) {\n        int n=s.size();\n        vector<int>t(2,-1);\n        int ans = 0;\n        for(int e=0;e<n;++e){\n            if(t[s[e] - \'0\'] == -1){\n                t[s[e]-\'0\'] = ans;\n                ans = ((long long)2*ans + 1)%M;\n            }\n            else{\n                int prev = ans;\n                ans = ((long long)2*ans - t[s[e]-\'0\'] + M)%M;\n                t[s[e] - \'0\'] = prev;\n            }\n        }   \n        \n        int final_ = ans;\n        ans = 0;\n        int val = 0;\n        t = {-1,-1};\n        for(int e=n-1;e>=0;--e){\n            if(t[s[e] - \'0\'] == -1){\n                t[s[e]-\'0\'] = ans;\n                val = ((long long)val + (s[e] == \'0\')*ans)%M;\n                ans = ((long long)2*ans + 1)%M;\n            }else{\n                int prev = ans;\n                val = ((long long)val + (s[e] == \'0\')*(ans - t[s[e]-\'0\'] + M))%M;\n                ans = ((long long)ans*2 - t[s[e]-\'0\'] + M)%M;\n                t[s[e]-\'0\'] = prev;\n            }\n        }\n        \n        final_ = ((long long)final_ - val + M)%M;\n        return final_;\n        \n        /*\n        The total no of unique good subsequences is the sum of the total distinct sequences - total_no of distinct \n\t\tsequences starting with 0. So to calculate the no of distinct sequences starting with 0, just traverse from the\n\t\tend and find the count of sequences ending at 0. (ending at 0 because we have traversed from the back of the\n\t\tarray so ending from back is same as calculating starting from front.)\n        */\n    }       \n};\n```
['Dynamic Programming']