aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-07-01 19:07:34 -0600
committerJack Sangdahl <[email protected]>2025-07-01 19:07:34 -0600
commit0d48f3681fc9ee8ef96d05537214aaf5d200927b (patch)
tree77db8c64d2616c104c07900845706ea92b4ef917
parentae7c434857555c74c4804d1cf9adc6d447e20e88 (diff)
downloadleetcode-0d48f3681fc9ee8ef96d05537214aaf5d200927b.tar.gz
leetcode-0d48f3681fc9ee8ef96d05537214aaf5d200927b.zip
3333. find the original typed string 2
-rw-r--r--find_original_typed_str2.c53
-rw-r--r--find_original_typed_str2.py50
-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}