Python | O(n) solution, think like a Trie, use O(1) space | Visual explanation | 13 lines
This question bugged me for a long time.\nI spent probably 3 hrs working on it.\nI had a solution in place but in reached TLE arround test 30.\nI finally found 
This question bugged me for a long time.\nI spent probably 3 hrs working on it.\nI had a solution in place but in reached TLE arround test 30.\nI finally found an O(n) time complex. solution with O(1) space complex.\n\nIt hit me that the permuations, the unique permutations, can be represented as a Trie:\n\nLet\'s assume the binary is "1101".\n\n**Step A - add "1"**\nWe now have a possiblity to add 1 zero, and 1 one.\nCounters[0] = 1\nCounters[1] = 1\nLength = 1\n\n![image](https://assets.leetcode.com/users/images/8293050f-bca6-439e-a4a5-290385ad7f9d_1644414579.2740688.png)\n\n**Step B - add "1"**\nThe additional "1" uses 1 One from our "One" bucket, but also allows a new "One" to be added.\nAfter adding it, we can add 2 zeros, or 1 one. So after adding the 1, our One bucket remains the same, but out zero bucket increase by the size of the One bucket\n\nCounters[0] = 2\nCounters[1] = 1\nLength = 1 + counters[1] = 1 + 1 = 2\n\n![image](https://assets.leetcode.com/users/images/04fff624-429b-4ebb-b7d7-3674f2bc67b1_1644414726.8433769.png)\n\n**Step C - add "0"**\nNow let\'s add a zero. Remember that we have a bucket of 2 Zeros, and indeed 2 Zeros we\'ll add.\nAfter that addition, 2 Zero will remain optional, but the number of Ones will increase from 1 to 3.\n\nCounters[0] = 2\nCounters[1] = 3\nLength = 2 + counters[0] = 2 + 2 = 4\n\n![image](https://assets.leetcode.com/users/images/5c1514b6-7fef-4e88-b6e5-f870bc28bf15_1644414849.9903631.png)\n\n**Step D - add "1"**\nIn this final step, we have a place for 2 Zeros, and 3 Ones. This "One" will use the bucket of 3.\n\nCounters[0] = 5\nCounters[1] = 3\nLength = 4 + counters[1] = 4 + 3 = 7\n\n![image](https://assets.leetcode.com/users/images/5096d51d-70bb-4e2f-addf-b232f24e5812_1644414918.9407954.png)\n\n\n**Remember a single "0"**\nIf there\'s a zero anywhere in our string, we\'ll need to remember to carry the single 0.\nsince "1101" has a zero, we\'ll add 1 to our length.\nlength = 7 + 1 = 8\n\nAnswer is indeed 8\n\n\nMy code\n\n```\nclass Solution:\n\tdef numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n\t\ttotal_len = 1\n\t\tif "0" in binary:\n\t\t\ttotal_len = 2\n\n\t\t# Remove left zero trailer, irrelevant\n\t\twhile i<len(binary) and binary[i] == "0": i+=1\n\t\tbinary = binary[i:]\n\n\t\t# Handle zeros only string\n\t\tif i == len(binary): return 1\n\n\t\t# Counters to count how many options to add zeros or ones uniquely exist.\n\t\t# Zeros in counters[0] and Ones in counters[1].\n\t\t# Populate first char manually\n\t\tcounters = [1,1]\n\t\tfor x in range(1,len(binary)):\n\t\t\tchar = binary[x]\n\t\t\tval = int(char)\n\n\t\t\t# Have the current char use all of the possible places to add based on "counters"\n\t\t\ttotal_len += counters[val]\n\t\t\t\n\t\t\t# Don\'t forget that if we used all the "ones", we created new "ones" and "zeros" opportunity\n\t\t\tcounters[abs(1-val)] += counters[val]\n\t\treturn total_len % 1000000007\n```\n\n\n\n
['Python']