[Java] - DP - O(N) time, O(1) space - explained
This problem is actually very similar to Distinct Subsequences, with 2 differences:\n1. Valid chars here are only 0 and 1\n2. No leading zeros is allowed\n\nThi
This problem is actually very similar to [Distinct Subsequences](https://leetcode.com/problems/distinct-subsequences-ii/), with 2 differences:\n1. Valid chars here are only `0` and `1`\n2. No leading zeros is allowed\n\nThis solution is less elegant than [awsome Lee\'s](https://leetcode.com/problems/number-of-unique-good-subsequences/discuss/1431819/JavaC%2B%2BPython-DP-4-lines-O(N)-Time-O(1)-Space), because I kept the idea of needing to count all sub-sequences, regardless of the allowed chars (using an array and not two vars), in order to help following the logic and understand how to conquer this problem.\n\n```\nclass Solution {\n    \n    private static final int MOD = 1000000007;\n    \n    public int numberOfUniqueGoodSubsequences(String binary) {\n        boolean addZero = false;        \n        int count = 1; // in the first round we "concat" to the empty binary\n        int[] countEndsWith = new int[2]; \n        for (int i=0; i<binary.length(); i++) {\n            char c = binary.charAt(i);\n            int cIndex = c-\'0\';\n            int endsWithCCount = count; // all valid sub-binaries + c at the end => same count\n            if (c == \'0\') {\n                addZero = true;\n                // every time c is \'0\', we concat it to "" and get "0" - we wish to count it only once (done in the end)\n                endsWithCCount--; \n            }\n            count = (count + endsWithCCount - countEndsWith[cIndex]) % MOD; // w/out c at the end minus dups (= already end with c)\n            count = count < 0 ? count + MOD : count; // may be negative due to MOD\n            countEndsWith[cIndex] = endsWithCCount;\n        }\n        count--; // remove the empty binary\n        if (addZero) count++; // add "0"\n        return count;\n    }\n}\n```
[]