diff options
-rw-r--r-- | find_original_typed_str2.c | 53 | ||||
-rw-r--r-- | find_original_typed_str2.py | 50 | ||||
-rw-r--r-- | find_original_typed_str2.{py} | 0 |
3 files changed, 103 insertions, 0 deletions
diff --git a/find_original_typed_str2.c b/find_original_typed_str2.c new file mode 100644 index 0000000..9d565f8 --- /dev/null +++ b/find_original_typed_str2.c @@ -0,0 +1,53 @@ +// 3333. Find the Original Typed String II +#include "leetcode.h" + +/* + * alice is attempting to type a specific string on her computer. however, she + * tends to be clumsy and may press a key for too long, resulting in a character + * being typed multiple times. you are given a string 'word', which represents + * the final output displayed on alice's screen. you are also given a positive + * integer 'k'. return the total number of possible original strings that alice + * might have intended to type, if she was trying to type a string of size at + * least 'k'. since the answer may be very large, return it modul 10^9+7. + */ + +int possibleStringCount(char *word, int k) { + long long prod = 1, mod = 1e9 + 7; + int g[2000], m = 0, n = strlen(word); + for (int i = 1, cnt = 1; i <= n; ++i) { + if (i < n && word[i] == word[i - 1]) + ++cnt; + else { + g[m++] = cnt - 1; + prod = (prod * cnt) % mod; + cnt = 1; + } + } + if (k <= m) + return (int)prod; + int dp[2][2001] = {{1}}, ps[2001] = {0}, sz = m; + for (int i = 0; i < sz; ++i) { + ps[0] = 0; + for (int j = 0; j < k - sz; ++j) + ps[j + 1] = (ps[j] + dp[i % 2][j]) % mod; + for (int j = 0; j < k - sz; ++j) { + int low = j - g[i]; + if (low < 0) + low = 0; + dp[!(i % 2)][j] = (ps[j + 1] - ps[low]) % mod; + if (dp[!(i % 2)][j] < 0) + dp[!(i % 2)][j] += mod; + } + } + long long ans = 0; + for (int i = 0; i < k; ++i) + ans = (ans + dp[sz % 2][i]) % mod; + return (int)((mod + prod - ans) % mod); +} + +int main() { + char *w1 = "aabbccdd", *w2 = "aabbccdd", *w3 = "aaabbb"; + printf("%d\n", possibleStringCount(w1, 7)); // expect: 5 + printf("%d\n", possibleStringCount(w2, 8)); // expect: 1 + printf("%d\n", possibleStringCount(w3, 3)); // expect: 8 +} diff --git a/find_original_typed_str2.py b/find_original_typed_str2.py new file mode 100644 index 0000000..42d2a1e --- /dev/null +++ b/find_original_typed_str2.py @@ -0,0 +1,50 @@ +# 3333. Find the Original Typed String II +from functools import reduce +from itertools import accumulate + +""" +alice is attempting to type a specific string on her computer. however, she +tends to be clumsy and may press a key for too long, resulting in a character +being typed multiple times. you are given a string 'word', which represents +the final output displayed on alice's screen. you are also given a positive +integer 'k'. return the total number of possible original strings that alice +might have intended to type, if she was trying to type a string of size at +least 'k'. since the answer may be very large, return it modul 10^9+7. +""" + + +class Solution(object): + def possibleStringCount(self, word, k): + """ + :type word: str + :type k: int + :rtype: int + """ + mod_mul = lambda a, b: (a * b) % (10**9 + 7) + mod_add = lambda a, b: (a + b) % (10**9 + 7) + mod_sub = lambda a, b: (a - b) % (10**9 + 7) + segment = [1] + for i in range(1, len(word)): + if word[i] != word[i - 1]: + segment.append(1) + else: + segment[-1] += 1 + total = reduce(mod_mul, segment) + if k <= len(segment): + return total + + dp = [1] + ([0] * (k - 1)) + for i in range(1, len(segment) + 1): + prefix = list(accumulate(dp, mod_add, initial=0)) + dp = [0] * k + for j in range(i, k): + dp[j] = mod_sub(prefix[j], prefix[j - min(segment[i - 1], j - i + 1)]) + less_than_k = reduce(mod_add, dp) + return mod_sub(total, less_than_k) + + +if __name__ == "__main__": + obj = Solution() + print(obj.possibleStringCount(word="aabbccdd", k=7)) + print(obj.possibleStringCount(word="aabbccdd", k=8)) + print(obj.possibleStringCount(word="aaabbb", k=3)) diff --git a/find_original_typed_str2.{py} b/find_original_typed_str2.{py} new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/find_original_typed_str2.{py} |