Python 3: TC O(N), SC O(1): Simple Code, Complicated Derivation and Proof
Intuition\n\nI left all of my thought process and stuff to show you that I did not have an easy time with this one.\n\nEventually I had to peek at @votrubac\'s 
# Intuition\n\nI left all of my thought process and stuff to show you that I did *not* have an easy time with this one.\n\nEventually I had to peek at @votrubac\'s solution. Even then I didn\'t really understand it and I had to fumble around with it some more.\n\nIn the end this turns out to be similar to DP, but not quite.\n\n## Uniques Versus Total\n\nThe total number is a lot easier to count with combinatorics. But the *unique* count is *much* more challenging.\n\nUltimately what I wound up doing was going through a complicated example problem, looking at the pattern, and fumbling around until I got something approximately right, then refined it into a solution.\n\nThis is @votrubac\'s approach. It works... if you have lots of time. If you\'re pitched this **in an interview though you don\'t have time to work through a complicated example problem.**\n\n## Interview Approach\n\nMy lesson learned with this problem is that if we need to count uniques, **we need to track the number of new sequences we\'ll get with each character.** This is the DP-like solution.\n\nZeros and ones are mostly symmetric situations except for the no leading zeros thing except for \'0\' itself. So **let\'s ignore a single leading zero for now.** **If there\'s a zero anywhere in the string we can add one at the end.**\n\n## Track What we Want: Numbers of New Subsequences\n\nSuppose we know, for each index, what `a0` and `a1` are; the number of new subsequences we get when appending a 0 or a 1 to all existing subsequences, respectively.\n\n## Let\'s Look at Appending Zeros\n\nNow let\'s look at all unique prefixes `p` where adding a zero results in a new prefix:\n* `p` is unique by assertion\n* `p0` is unique by definition\n\nIf we add another `0` in a row, then for each `p` we\'d have\n* `p`\n* `p0`\n* `p00`\n\nThe number of new sequences is the count of `p`. This continues, so we find that **if we keep appending zeros, then the number of new subsequences doesn\'t change.** That\'s because we only get a new subsequence for the situation were added zero every single time, which is only true for the original subsequences `p` before we started appending zeros.\n\nThe same logic applies for ones.\n\n**So we want to store the number of subsequences `p` where adding a zero creates a new unique subsequence, and same for ones.** We\'ll call those `a0` and `a1`, "added subsequences via 0/1"\n\nNow let\'s suppose we added a one instead. We\'ll add `a1` new subsequences by assumption. For each of those `a1` subsequences `p\'` we\'ll get a new unique subsequence `p\'1`.\n\nHow does this change `a0`? The only new subsequences we added are `p\'1`, so the change is somewhere in 0..`p\'1`. Any other subsequences we could append a 0 to and get a new subsequence are still there.\n\nLet\'s look at the result of adding 0 to each of those `p\'1`. We\'ll get `p\'10`. Are these all unique?\n\nLet\'s do a proof by contradiction. Suppose `p\'10` is NOT unique, that we already had it. To have gotten `p\'10` before though, we\'d have to have seen\n* `p\'` already, otherwise we can\'t have added a `10` later\n* `p\'1` already, otherwise we can\'t have added the last `0`\n\nBut that means we saw `p\'1` already, which is a contradiction because we just said that `p\'` by definition are all the prefixes where adding a `1` is a brand new subsequence.\n\nTherefore we have proven that all the `p\'10` are new subsequences.\n\n## How a0 and a1 Change at Each Index\n\nSo finally we learn that\n* suppose we add `a0` subsequences when we see a `0`, and `a1` if we see a 1\n* if we see a 0, then `a0` doesn\'t change: this is the `p -> p, p0 -> p, p0, p00 -> ...` stuff\n* if we see a 1, then all the new `a1` subsequences of the form `p\'1` will yield a new subsequence `p\'10` if we append a `0`, proved by contradiction. So in addition to the `a0` we had before, we gain `a1` new subsequences\n\nTherefore:\n* when we see a `0`: `a0` doesn\'t change, `a0 += a1`\n* when we see a `1`: `a1` doesn\'t change, `a1 += a0`\n* and `total` increases by `a0` or `a1`, whichever one corresponds to the character we just saw\n\n# Approach\n\nIf there\'s a zero anywhere in the string then we\'ll have one special number that is just "0". It doesn\'t follow the append rules because you can\'t have `00` or `01`.\n\nIf there no zero then we know the answer, it\'s the length because we have `1`, `11`, `111`, etc. One to `len(binary)`.\n\nTherefore we handle `0` separately.\n\nThis means that at the start\n* if we add a `1`, we get one new subsequence: `0 -> 0, 1`\n* if we add a `0`, we get zero new subsequences: `0 -> 0`\n\nThis will make `total` the count of all subsequences starting with a one. Therefore at the end we add `+1` to account for the single binary subsequence of `0` itself.\n\n# Final Thoughts\n\nI think "count the uniques" problems require a different thought process, one similar to DP but not quite the same.\n\nThis is really more similar to the "quick update trick," where you record how values change at each index, then find a fast way to update that in `O(1)`.\n\nIn this case the problem was solved easily in the end (although the derivation and proof are tricky) by recording\n* the number of new subsequences we get when appending a 0\n* the number we get when appending a 1\n\nAnd then updating those.\n\nThis is conceptually a lot easier than the LC hint, which is to use DP. That\'s possible, but I think LC\'s idea is that we can effectively compute `a0` and `a1` as tracked here using the change in uniques we saw the last time we saw each digit. That works, but it\'s kind of ugly and roundabout. It\'s just easier to say "we want to know how `total` changes if we see either digit, and know how `a0` and `a1` change at each element."\n\nThe code is easier this way; many other solutions have more complicated `ans_i - ans_{i-1} + ..` stuff. It\'s mathematically equivalent but this just seems a lot cleaner.\n\n# Complexity\n- Time complexity: linear\n \n- Space complexity: constant\n\n# Code\n```\nclass Solution:\n    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n        # subseq of binary is good if\n        #   > not empty\n        #   > no leading zeros (except 0 itself)\n\n        # number of unique good subsequences\n\n        # subSEQUENCE, not subARRAY\n\n        # ways to make a unique subsequence: take the number with length l and append or prepend a digit\n\n        # what if we count total unique subsequences then account for leading zeroes later?\n\n        # for total subsequences:\n        #    suppose we have all uniques up to i\n        #    then we append binary[i]\n          \n        # ugh, dont\' know if appending will make a new unique\n\n        # other idea:\n        # starting with one one, or two ones, or three ones, etc. are all  unique\n        # then we take 1+ zeros\n        # etc.\n        # these are all unique\n\n        # suppose we have uniques split up by prefix, e.g. those starting with 1+ ones and 1+ zeros\n        # then when we add a new char, e.g. 1\n        #    adding 1 one may or may not make a new unique if prepending to zero\n        #\n        # so this isn\'t a good way to split up the problem\n\n        # all possible subsequences: 2**len-1 (nonempty)\n\n        # can we count duplicates quickly?\n\n        # WAIT: for each stretch of ones and zeros:\n        #   we can take any number of ones and at least one zero, then continue\n        #   that "then continue" will return all\n\n        # UGH THIS IS HARD\n        #\n        # Can\'t find the right subproblem, I\'m sure it\'s something like O(1) DP as we proceed but I can\'t get it\n        #\n        # for 0000000 there\'s only one\n        #  for 100000 there\'s 1, 10, 100, 100, ... so len + 1 including 0 itself\n        #  for 101010 there\'s\n        #        1, 11, 111\n        #        10, 110, 1110\n\n        # so let\'s return to number of uniques starting with each number of ones and zeros; anything that\'s 0001... is diff from 001...\n        #\n        # so if we have u unique combinations starting with a one after some index i\n        #   then each of the leftZeros\n        #\n        \n        # HINT: number of uniques is the number of unique decimal values, which makes sense\n        # each distinct number is a distinct subsequence\n\n        # HINT 2: find the answer at each indedx based on the previous indexes\' answers\n\n        # so left-to-right DP... which I knew already basically\n\n        # if we have a bunch of uniques up to i\n        #    > if they\'re maximum length thus far, then adding a new digit is a new value\n        #    > otherwise it might not be\n\n        # maybe once again we get all uniques ending with each number of zeros and ones\n        #    if current digit is one: all uniques ending with zero, plus a 1, is a new unique\n        #                             all uniques ending with one, plus a 1, gets complicated\n        #              e.g. 1, 11, 111\n        #                   101, 1001\n        #   adding a 1 gives 11, 111, 1111 => only the max ones gets larger\n        #         but 1011, 10011 are uniques too\n        #\n        # can\'t solve, need to peek at solutions\n\n        # votrubac: get transition formula from a nontrivial example, knowing we want O(1) idx-to-idx update\n\n        # e.g. 0 0 1 0 1 0 0 1 0\n        #\n        # 0:  0\n        # 0:  0\n        # 1:  0, 1                                                     +1 (2)\n        # 0:  0, 1, 10                                                 +1 (3)\n        # 1:  0, 1, 10, 11, 101                                        +2 (5)\n        # 0:  0, 1, 10, 11, 101, 100, 110, 1010                        +3 (8)\n        # 0:  0, 1, 10, 11, 101, 100, 110, 1010, 1000, 1100, 10100     +3 (11)\n        # 1:  0, 1, 10, 11, 101, 100, 110, 1010, 1000, 1100, 10100, 111, 1011, 1001, 1101, 10101, 10001, 11001, 101001  +8 (19)\n\n\n        # something about\n        #    > get the new sequences we got when we added a 1\n        #    > if we add another one, we get the same number of new sequences\n        #    > the new sequences are\n        #         > all sequences\n        #         > minus the ones that are the same if we add a 1\n        #         > the latter is the number we added the first time we saw a 1 in this stretch\n\n        # track the number of new sequences we get if we add either digit\n        if not any(c == \'0\' for c in binary): return len(binary)\n\n        # ignore special case of leading zero to start\n\n        BIG = 10**9 + 7\n\n        # record the number of new sequences we get if we add a 0 and a 1\n        a0 = 0\n        a1 = 1\n        total = 0\n        for c in binary:\n            if c == \'0\':\n                total = (total + a0) % BIG\n                a1 = (a1 + a0) % BIG\n            else:\n                total = (total + a1) % BIG\n                a0 = (a0 + a1) % BIG\n\n        return total + 1 # leading zero\n\n        # Hokay, lucky guess. Now why?\n\n        # if we have a0 prefixes where adding a zero makes a new sequence\n        # then we indeed add a zero: for each of those a0 we have p and p0 now\n        # then when we add another zero, we get p, p0, p00: only the ones we added a zero to *and were unique* are new uniques with 00\n        # that\'s a0 still\n        #\n        # for each of those p, p0, p00, ...\n        # if we add a 1 then all of those p01, p001, etc. are new (?)\n        # suppose p01 is NOT new\n        # that means we already had a p01 before\n        # and before making p01 we must have had p0\n        # but we just said that p0 was new\n        # therefore this leads to a contradiction\n\n        # start with p, prefixes where adding a zero is unique. that means p0 does NOT exist\n        #     so adding a zero: means we get p, p0 for all p\n        #     add another zero: we get p, p0, p00 for all p\n        #     etc: each zero adds a number of sequences equal to p\n        #\n        # now if we add a 1:\n        #     suppose we have the count of p\' where p\'1 is new; p\'1 is not among the sequences we have\n        #     are all the p0 part of p\'?\n        #     suppose p0 is not part of p\'. that means p01 already exists in p\'\n        #     for that to be true, we must have had p0 already before seeing an earlier 1\n        #         that means p0 is part of p\n        #         but that contradicts the fact that p by definition is a prefix | p0 has not been seen before\n        #     therefore p01 is new\n        #     and p001 is new\n        #     and so on\n```
['Python3']