Without DP - Every 0/1 after first 1's doubles total count - Easy to understand
If you want to understand another solution this is also very interesting\nhttps://stackoverflow.com/questions/46608552/unique-subsequences-for-a-binary-array\nO
If you want to understand another solution this is also very interesting\nhttps://stackoverflow.com/questions/46608552/unique-subsequences-for-a-binary-array\nOriginal paper: https://doi.org/10.1016/j.tcs.2008.08.035 (Read only these two topics: Preliminaries and Counting distinct subsequence)\n\nAlthough none of the codes mentioned there will work, because 1. Code is not correct 2. It is not very specialised to this prblm.\n\nBased on the ideas mentioned there I have implemented my own solution:\n\nSpace `O(1)`\nTime `O(n)`\n\n```c++\n#define MOD 1000000007\nclass Solution {\npublic:\n    int numberOfUniqueGoodSubsequences(string s) {\n        int count = 1, n = s.size(), k=0, zero=0;\n        map<char,int> seen;\n    \n        while(k<n && s[k]==\'0\') k++;\n        if(k==n) return 1;\n        for(int i=k+1; i<n; i++){\n            int temp = count;\n            char ch=s[i];\n            count = (count*2)%MOD;\n            if(seen[ch])\n                count -= seen[ch];\n            seen[ch] = temp%MOD;\n            if(count<0) count += MOD;\n        }\n        zero = s.find("0")!=string::npos;\n        return (count+zero)%MOD;\n    }\n};\n```\n\nThanks @lee215\nI was missing few edge cases which I got from your solution.\n\nWill share a detailed explanation of this solution soon.\n\nUpvote if it helped you.
[]