[Python] 7 lines dp solution, explained
This problem is very similar to problem 940. Distinct Subsequences II, so if you already solved or at least have seen it, it will help a lot. The idea is to use
This problem is very similar to problem **940. Distinct Subsequences II**, so if you already solved or at least have seen it, it will help a lot. The idea is to use `dp`, where `dp[i]` is number of unique subsequences for string `S[0], ... S[i]` - which do not start with **0** (we will deal with `0` case in the end). Then, each time we add symbol we need to do the following:\n\n1. Imagine that we have `t1, t2, ..., tk` unique subsequences for `i-1`. We also have options `t1 + S[i], t2 + S[i], ..., tk + S[i]`.\n2. However some of strings are the same, exactly for this we keep dictionary `last`: is the last place for each symbol so far. So, we subtract `dp[last[x]]` number of options. \n3. Also if we meet symbol `0` for the first time, we need to subtract `1`.\n\nLet us go through example `S = 111000101` and see what what options we have:\n\n1. `dp[0] = 1`, we have only one option: empty string `""`.\n2. Consider next symbol: `1`, we have `"", 1`, `dp[1] = 2.`\n3. Consider next symbol: `1`. We need to double number of options: we have `4` of them: `"", 1` and `1, 11` but one of them is repetition, it is `dp[last[1]]`, so we have options `"", 1, 11` and `dp[3] = 3`.\n4. Similarly `dp[4] = 4` and we have options `"", 1, 11, 111`.\n5. Now we have element `0` and we meet it for the first time, so we have `"", 1, 11, 111`, `0, 10, 110, 1110`. We need to remove option `0` at the moment, so we have `"", 1, 11, 111, 10, 110, 1110` and `dp[5] = 7`.\n6. Now we have again element `0`. We meet it not for the first time, so we have previous options `"", 1, 11, 111, 10, 110, 1110`, new options are `0, 10, 110, 1110, 100, 1100, 11100`. How many of this options are intersect: it is `10, 110, 1110` and also we need to remove "0", so optoins we are not happy with is `0, 10, 110, 1110`, which is exaclty what we had on step `4` but with added `0`.\n7. I think you understand the logic now and can continue this for the rest of the string: I leave it to you as exercise, put your solutions in comments :)\n\nIn the end we need to deal with `0` case: we need to subtract `-1` for empty set and add `int("0" in S)` to check if we have `0` in our string.\n\n#### Complexity\nTime complexity is `O(n)`, space complexity also `O(n)`.\n\n#### Code\n```python\nclass Solution:\n    def numberOfUniqueGoodSubsequences(self, S):\n        dp, last = [1], {}\n        for i, x in enumerate(S):\n            dp.append(dp[-1] * 2)\n            dp[-1] -= dp[last[x]] if x in last else int(x == "0")\n            dp[-1] = dp[-1] % (10**9 + 7)\n            last[x] = i\n\n        return dp[-1] - 1 + int("0" in S)\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Dynamic Programming']