[Python] simple DP solution with thinking process and pattern explanation
I couldn\'t solve this problem during the contest. \nAnd it actually took me quite a while to understand the solutions in the Discussion (but they are very help
I couldn\'t solve this problem during the contest. \nAnd it actually took me quite a while to understand the solutions in the Discussion (but they are very helpful!).\nI hope my thinking process in the following can be also helpful to others.\n\nLet\'s use **dp0 & dp1** to represent the number of unique subsequences that end with 0 and 1 respectively.\n\n**- Wrong idea -**\nWhen I derived the DP equation during the contest, I was thinking about sth like **dp1 = 2 * dp1 + dp0 + ...**, where factor **2** comes from the fact that \nwhen we see 1, we can choose to `add` or `not add` 1 to the previous subsequences that end with 1. And the resulting subsequences will all end with 1.\nThis is clearly wrong because subsequences [1, 11] will become [1, 11, 11, 111] where 11 is doubly counted.\n\n**- Pattern in subsequences -**\nAfter reading several solutions, I went through examples and realized I ignored a pattern in the subsequences.\nLet\'s name the two groups of unique subsequences that end with 0 and 1 as **G0 & G1** respectively.\n* In **G1**, for example, if say 110100**111** exists, then 110100**11** and 110100**1**  must also exist!\n* In the meantime, in **G0** 110100 must exist.\n\nSo when we iterate over the string and see a "1", we can add it to all of them in **G1** [..., 110100**111**, 110100**11**, 110100**1**, ...] --> [..., 110100**1111**, 110100**111**, 110100**11**, ...], and the orignally last one 110100**1**, which was missing then, can be generated _again_ from **G0** [..., 110100, ...] --> [..., 110100**1**, ...]\n\nAs a result, the new **G1*** has two parts:\n1. subsequences whose length of consecutive "1" in the end `L == 1`. They come from previous **G0**, each adding a "1".\n2. subsequences with `L > 1`, which come from previous **G1**.\n\nThe first part covers all the subsequences with `L == 1` that were previously in **G1**.\n\n\n```\nclass Solution:\n    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n        \n        dp0, dp1 = 0, 0   # number of unique subsequences that end with 0 or 1\n        for val in binary:\n            if val == \'0\':\n                if dp0 == 0:\n                    dp0 = dp1 + 1    # add "0" to dp0 related subsequences group\n                else:\n                    dp0 = (dp0 + dp1) % (10 ** 9 + 7)\n            else:\n                if dp0 == 0:\n                    dp1 = dp1 + 1\n                else:\n                    dp1 = (dp0 + dp1) % (10 ** 9 + 7)\n        return (dp0 + dp1) % (10 ** 9 + 7)\n```
[]