O(n) solution 68ms Beats 80.00% of users with JavaScript
Intuition\nThe code is designed to count the number of unique good subsequences in a binary string. A good subsequence is one that starts with \'1\' and ends wi
# Intuition\nThe code is designed to count the number of unique good subsequences in a binary string. A good subsequence is one that starts with \'1\' and ends with \'0\'. It uses dynamic programming to efficiently track the counts of such subsequences ending with \'0\' and \'1\'. The presence of \'0\' is important, and if it is found in the string, an extra count of 1 is added to account for the subsequence \'0\'. By iteratively processing the characters, the code calculates the result modulo 10^9 + 7 to prevent integer overflow. \n\n# Approach\n\n\nInitialize two counters, endsWithZero and endsWithOne, to track the counts of good subsequences ending with \'0\' and \'1\' in the binary string.\n\nInitialize a flag variable, hasZero, to determine if \'0\' has been encountered in the string. This flag is used to decide whether an additional count needs to be added.\n\nIterate through the binary string character by character.\n\nWhen encountering \'0\', update endsWithZero by adding the current count of subsequences ending with \'1\'. Set hasZero to 1 to indicate the presence of \'0\'.\n\nWhen encountering \'1\', update endsWithOne by adding the counts of subsequences ending with \'0\' and \'1\' and incrementing by 1 to account for the current \'1\'.\n\nAfter processing the entire string, return the total number of unique good subsequences. If \'0\' is present in the string (hasZero is 1), add 1 to the result to account for the case where \'0\' itself is a good subsequence. \n\n\n\n# Complexity\n- Time complexity:\n O(n) - Linear time due to a single pass through the binary string. \n\n- Space complexity:\n O(1) - Constant space is used for variables; no additional data structures.\n\n# Code\n```\n/**\n * @param {string} binary\n * @return {number}\n */\n\nvar numberOfUniqueGoodSubsequences = function(binary) {\n    // Define a constant MOD for later modulo operations\n    const MOD = Math.pow(10, 9) + 7;  // Set the constant MOD to 10^9 + 7\n    \n    // Initialize counts for subsequences \n    let endsWithZero = 0;\n    let endsWithOne = 0;\n    \n    // Initialize a variable to track if \'0\' has been seen in the string\n    let hasZero = 0;\n    \n    // Iterate through the binary string character by character\n    for (let i = 0; i < binary.length; i++) {\n        // Check if the current character is \'0\'\n        if (binary[i] === \'0\') {\n            // Calculate the count of subsequences ending with \'0\'\n            endsWithZero = (endsWithZero + endsWithOne) % MOD;\n            \n            // Set the \'hasZero\' flag to 1, indicating \'0\' has been seen\n            hasZero = 1;\n        } else {\n            // Calculate the count of subsequences ending with \'1\'\n            // These can be formed by adding \'1\' to both \'0\' and \'1\' subsequences\n            endsWithOne = (endsWithZero + endsWithOne + 1) % MOD;\n        }\n    }\n\n    // If \'0\' is present in the string, add 1 to the result; otherwise, use only endsWithOne\n    return (endsWithOne + (hasZero + endsWithZero)) % MOD;\n};\n```
['String', 'Dynamic Programming', 'JavaScript']