diff options
author | Jack Sangdahl <[email protected]> | 2024-12-30 11:34:50 +0100 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-30 11:34:50 +0100 |
commit | 00d43ad8605d97544c17cb1775ca884ef0857869 (patch) | |
tree | 7cd0ff4edea0da139aa88b7c7766fd283b5ea7b4 | |
parent | 8aedb21321ae40254e4ee6b7fcd4c3de77096964 (diff) | |
download | leetcode-00d43ad8605d97544c17cb1775ca884ef0857869.tar.gz leetcode-00d43ad8605d97544c17cb1775ca884ef0857869.zip |
2466. count ways to build good strings
-rw-r--r-- | count_ways_build_strs.c | 9 | ||||
-rw-r--r-- | count_ways_build_strs.cpp | 17 | ||||
-rw-r--r-- | count_ways_build_strs.py | 36 |
3 files changed, 48 insertions, 14 deletions
diff --git a/count_ways_build_strs.c b/count_ways_build_strs.c index 3a357eb..0692a2a 100644 --- a/count_ways_build_strs.c +++ b/count_ways_build_strs.c @@ -1,6 +1,5 @@ // 2466. Count Ways To Build Good Strings -#include <stdio.h> -#include <stdlib.h> +#include "leetcode.h" /* * given the integers 'zero, one, low, and high', we can construct a string by @@ -15,9 +14,8 @@ */ int countGoodStrings(int low, int high, int zero, int one) { - int mod = 1e9 + 7; - int *dp = calloc(high + 1, sizeof(int)); - long long ans = 0; + int mod = 1e9 + 7, ans = 0; + int *dp = (int *)calloc(high + 1, sizeof(int)); dp[0] = 1; for (int i = 1; i <= high; i++) { if (i >= one) @@ -27,6 +25,7 @@ int countGoodStrings(int low, int high, int zero, int one) { if (i >= low) ans = (ans + dp[i]) % mod; } + free(dp); return ans; } diff --git a/count_ways_build_strs.cpp b/count_ways_build_strs.cpp index 7600fa3..d388b2f 100644 --- a/count_ways_build_strs.cpp +++ b/count_ways_build_strs.cpp @@ -16,19 +16,18 @@ class Solution { public: int countGoodStrings(int low, int high, int zero, int one) { + int mod = 1e9 + 7, ans = 0; vector<int> dp(high + 1, 0); dp[0] = 1; - int mod = 1000000007; - for (int i = 1; i <= high; ++i) { - if (i >= zero) - dp[i] += dp[i - zero] % mod; + for (int i = 1; i <= high; i++) { if (i >= one) - dp[i] += dp[i - one] % mod; + dp[i] = (dp[i] + dp[i - one]) % mod; + if (i >= zero) + dp[i] = (dp[i] + dp[i - zero]) % mod; + if (i >= low) + ans = (ans + dp[i]) % mod; } - long long cnt = 0; - for (int i = low; i <= high; ++i) - cnt = (cnt + dp[i]) % mod; - return cnt; + return ans; } }; diff --git a/count_ways_build_strs.py b/count_ways_build_strs.py new file mode 100644 index 0000000..26a2530 --- /dev/null +++ b/count_ways_build_strs.py @@ -0,0 +1,36 @@ +# 2466. Count Ways To Build Good Strings +from collections import Counter + +""" +given the integers 'zero, one, low, and high', we can construct a string by +starting with an empty string, and then at each step perform either of the +following opperations: +- append the character 0 'zero' times +- append the character 1 'one' times +this can be performed any number of times. a good string is a string +constructed by the above process having a length between 'low' and 'high' +(inclusive). return the number of different good strings that can be +constructed. return modulo 10^9+7. +""" + + +class Solution(object): + def countGoodStrings(self, low, high, zero, one): + """ + :type low: int + :type high: int + :type zero: int + :type one: int + :rtype: int + """ + dp = Counter({0: 1}) + mod = 10**9 + 7 + for i in range(1, high + 1): + dp[i] = (dp[i - zero] + dp[i - one]) % mod + return sum(dp[i] for i in range(low, high + 1)) % mod + + +if __name__ == "__main__": + obj = Solution() + print(obj.countGoodStrings(3, 3, 1, 1)) + print(obj.countGoodStrings(2, 3, 1, 2)) |