[Rust / Elixir] bottom-up DP
Approach\nIterate the string from right to left, and maintain 3 variables:\nans: Number of unique good subsequences so far, excluding "0".\nsuffix: Number of un
# Approach\nIterate the string from right to left, and maintain 3 variables:\n`ans`: Number of unique **good** subsequences so far, excluding `"0"`.\n`suffix`: Number of unique subsequences starting with `"0"`, and also including the empty string `""`.\n`has_0`: Records if there is any `"0"` found, so that we can add 1 to the final answer.\n\nCase 1: When a `"1"` is encountered, increase `ans` by `suffix`.\nCase 2: When a `"0"` is encountered, increase `suffix` by `ans + 1`, and also set the `has_0` flag.\n# Why does it work\nWe can guarantee that in Case 1, we can find exactly (`suffix`) new unique **good** subsequences to add to `ans`. Let\'s say when for the 1st time we encounter a `"1"` after `str` is included to `suffix`, we can create `"1str"`, and the 2nd time we can create `"11str"`, 3rd time `"111str"` etc...\n\nSame logic for Case 2, i.e. `"0str"`, `"00str"`, `"000str"` etc..., except that we need to add 1 more which is a new unique subsequence of just `"0"`s, i.e. `"0"`, `"00"`, `"000"` etc...\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(1)$$\n\n# Code\n```Rust []\nimpl Solution {\n    pub fn number_of_unique_good_subsequences(binary: String) -> i32 {\n        let mut ans = 0;\n        let mut suffix = 1;\n        let mut has_0 = 0;\n        let large = 1_000_000_007;\n        for b in binary.bytes().rev() {\n            if b == b\'0\' {\n                suffix = (ans + suffix + 1) % large;\n                has_0 = 1;\n            }\n            else {\n                ans = (ans + suffix) % large;\n            }\n        }\n        ans + has_0\n    }\n}\n```\n```Elixir []\ndefmodule Solution do\n  @large 1_000_000_007\n\n  @spec number_of_unique_good_subsequences(binary :: String.t) :: integer\n  def number_of_unique_good_subsequences(binary) do\n    String.to_charlist(binary)\n    |> List.foldr({0, 1, 0}, fn\n      ?0, {ans, head0, _} -> {ans, rem(head0 + ans + 1, @large), 1}\n      ?1, {ans, head0, has_0} -> {rem(ans + head0, @large), head0, has_0}\n    end)\n    |> then(fn {ans, _, has_0} -> rem(ans + has_0, @large) end)\n  end\nend\n```
['Dynamic Programming', 'Rust', 'Elixir']