Count Ways To Build Good Strings
by atalaykutlay
Solution to Leetcode problem Count Ways To Build Good Strings in Javascript.
1/**
2 * @param {number} low
3 * @param {number} high
4 * @param {number} zero
5 * @param {number} one
6 * @return {number}
7 */
8var countGoodStrings = function(low, high, zero, one) {
9 let dp = new Array(high+1).fill(0);
10 dp[0] = 1;
11 let ans = 0;
12 for (let i = 1; i <= high; i++) {
13 dp[i] = ((i-zero>=0 ? dp[i-zero]:0)+(i-one>=0 ? dp[i-one]:0))%1000000007;
14 if (i >= low) {
15 ans = (ans+dp[i])%1000000007;
16 }
17 }
18 return ans;
19};✨ Code Explanation ✨
This code counts the number of "good strings" that can be formed using "0" and "1" with length between "low" and "high" (inclusive), and have at most "zero" number of "0"s and at most "one" number of "1"s. The function creates an array "dp" of length "high+1" and fills it with 0. The value of "dp[i]" represents the number of good strings that can be formed with length "i". It initializes "dp[0]" to 1, since there is only one good string of length 0 - an empty string. Then, it uses dynamic programming to calculate the values of "dp[i]" for all i between 1 and high. It does this by adding the number of good strings that end in a "0" (i.e., length "i-1" strings with at most "zero" "0"s) and the number of good strings that end in a "1" (i.e., length "i-1" strings with at most "one" "1"s). It updates the value of "ans" to be the sum of all good strings between "low" and "high". Finally, it returns the value of "ans". The code uses modulo arithmetic to prevent integer overflow.
Share
