O(N) using unique subsequences II
\n\n\nclass Solution {\npublic:\n    int mod = 1e9 + 7;\n\nint numberOfUniqueGoodSubsequences(string s)\n{\n\n    unordered_map<char, int> index; //stores updat
![image](https://assets.leetcode.com/users/images/e493b820-6039-4ae6-83b0-77f5f432743e_1660615824.5193138.png)\n\n```\nclass Solution {\npublic:\n    int mod = 1e9 + 7;\n\nint numberOfUniqueGoodSubsequences(string s)\n{\n\n    unordered_map<char, int> index; //stores updated index of current  element\n    vector<long long> v(s.size() + 1, 0); //stores no. of subsequences\n\n    v[0] = 1;  // empty subsequence\n\n\t//index of first zero\n    int firstZero=-1;\n   \n    for (int i = 1; i <= s.size(); i++)\n    {\n\n\t\t//expected value is twice of previous subsequences by taking current element or rejecting it\n\t\t//suppose subseq-{1,11,111} =3 elements and current item =\'0\' then expected values are \n\t\t//{1,11,111,10,110,1110} = 2*3 =6\n\t\t\n        long long expected = (2 * v[i - 1]) % mod;\n\n        if (index.find(s[i - 1]) != index.end())  //if item already present\n        {\n\t\t\t//subtract the subsequences formed by last current element with its previous element\n\t\t\t//if current element =\'0\' then previous \'0\' has already formed some subsequences with its previous element\n            v[i] = expected - v[index[s[i - 1]] - 1];\n        }\n        else //first apprearance\n        {\n            v[i] = expected;\n\n\t\t\t//if its first zero then remove that zero to avoid further subsequences starting with 0\n            if(s[i-1]==\'0\'){\n                v[i]--;\n                 \n                firstZero =i-1;\n            }\n        }\n\n        index[s[i - 1]] = i;\n\n    }\n    \n     while(v[s.size()]<0){\n            v[s.size()]+=mod;\n        }\n\t\n\t//if a zero is present then add that first zero to final answer \n\t//also remove empty subsequence from answer\n    return  (firstZero!=-1) ? (v[s.size()])%mod : (v[s.size()-1] ) %mod ;\n}\n \n};\n```
['Dynamic Programming', 'C']