C++ Detail explanation
When we see that problem, the first solution we appear in our head is using recursion to find the subsequences and we push this string into a map with key => va
When we see that problem, the first solution we appear in our head is using recursion to find the subsequences and we push this string into a map with key => value or tuple to get the unique string. After that we return the size as a result of problem. This solution is nice, it\'s can solve the problem, but the constrain of the problem not allow we to do this easily. \n \n `1 <= binary.length <= 10^5` with this constrain if we using recursion the time complexity is very huge. The solution will be **Time Limit Exceeded**. Because of that, we need another appoard. Let\'s find out better solution with **O(N)** runtime complexity and **O(1)** space complexity.\n \nWe split this problem into smaller problems, the question is "*If I add a new number to a string, how many new subsequences can I have?*"\n\nFind the number of **unique good subsequences** of `binary`. The good subsequences just is the subsequences **without leading zero**. To be easily handle the case zero leading, it\'s better for us when going from last element to first element and now the question became "*If I add a new number to a head of string, how many **unique subsequences** can be create?*".\n\n`binary consists of only \'0\'s and \'1\'s.` depend on that constrain, elements we can add to head of string just be `1` or `0`. \n\n"*How many unique subsequences can be create?*"\nExample: \n- We have a empty string like `""` so our `subsequences` will be `[]`. \n\nBecause each subsequences is **unique**, that mean we just can be add sequences \'1\' and \'0\' only one time. To hadle this we create a flag to mark sequence `1` and `0` had appear or not.\n- `If number == \'1\'`:\n\t- We add a `1` to string. String is `"1"` so `subsequences` become `["1"]` => number of unique subsequences we create be `1`.\n\t- We add new `1` to head of string like `"11"`. `The subsequences` is `["1", "11"]` => number of unique subsequences we create be `1`.\n\t- `...` and so on with string `"1111"`. `The subsequences` is `["1", "11", "111", "1111"]` => number of unique subsequences we create still be `1`.\n\t\tSo we have procedural code: \n\t\t```\n\t\tresult = 0\n\t\tuniqueSubsequence = 0\n\t\tone = true\n\t\t\n\t\tfrom last number to first number: \n\t\t\tif number == \'1\':\n\t\t\t\tif one == true:\n\t\t\t\t\tuniqueSubsequence += 1\n\t\t\t\t\tone = false\n\t\t\t\t\n\t\t\tresult += uniqueSubsequence\n\t\t```\n- `If number == \'0\'`:\n\t- We add a `0` to string. String is `"0"` so `subsequences` become `["0"]` => number of unique subsequences we create be `1`. Simple, right!\n\t- Add a new `0` to a string. String become `"00"` but `subsequences` still `["0"]`, cause good subsequences is not have leading zero except `"0"` so not like `1`, `0` only add new unique subsequences at first time this appear => number of unique subsequences we create be `0`. \n\tOur procedural code become: \n\t\t\n\t\t``` \n\t\tresult = 0\n\t\tuniqueSubsequence = 0\n\t\tone = true\n\t\tzero = true\n\n\t\tfrom last number to first number: \n\t\t\tif number == \'1\':\n\t\t\t\tif one == true:\n\t\t\t\t\tuniqueSubsequence += 1\n\t\t\t\t\tone = false\n\t\t\t\tresult += uniqueSubsequence\n\t\t\t\t\n\t\t\tif number == \'0\':\n\t\t\t\tif zero == true:\n\t\t\t\t\tuniqueSubsequence += 1\n\t\t\t\t\tresult += 1\n\t\t\t\t\tzero = false\n\t\t```\n\n- What if we add `0` to a string `"11"`. The string become "011" and the `sequences` be `["1", "11", "0"]`. Right!\n- And we add a `1` to head of this string. Now string become `"1011"`. So how many subsequences can we create now? \n\t\nHead back to last step when string became `"011"`. Our `sequences` actually be something like `["1", "11", "0", "01", "011"]` , but we have to remove `"01"` and `"011"` cause their are not a good subsequences. When we add a new number `1` to head the `sequences` became `["1", "11", "0", "111" "10" "101", "1011"]` not just `["1", "11", "0", "111", "10"]`. \n\t\nWhat is that mean? That mean when we face a `0` leading we have to track all the **last result** (the path `["1", "11"]`) like the unique subsequence because we will remove all their not good subsequence (the path `["01", "011"]`) in the next step. \n\nLet\'s complete our procedural code:\n``` \nresult = 0\nuniqueSubsequence = 0\none = true\nzero = true\n\nfrom last number to first number: \n\tif number == \'1\':\n\t\tif one == true:\n\t\t\tuniqueSubsequence += 1\n\t\t\tone = false\n\t\tresult += uniqueSubsequence\n\n\tif number == \'0\':\n\t\tuniqueSubsequence += result\n\t\tif zero == true:\n\t\t\tuniqueSubsequence += 1\n\t\t\tresult += 1\n\t\t\tzero = false\n\nreturn result\n```\n\nOk that is everything of this problem! Here is my C++ code:\n```\nclass Solution {\npublic:\n    int numberOfUniqueGoodSubsequences(string binary) {\n        long res = 0,\n            unqCase = 0,\n            len = binary.length();\n        \n        bool zero = true,\n             one = true;\n        \n        for (int i = len - 1; i >= 0; --i) {\n            if (binary[i] == \'1\') {\n                if (one) {\n                    unqCase++;                    \n                    one = false;\n                }\n                \n                res += unqCase;\n            } else {\n                unqCase += res;\n                \n                if (zero) {\n                    unqCase++;\n                    res++;\n                    zero = false;\n                }\n            }\n            \n            res %= (long) 1e9+7;\n        }\n\n        return res;\n    }\n};\n```\n\n**Conclusion:**\n- Runtime complexity: **O(N)**\n- Space complexity: **O(1)**
['C', 'C++']