aboutsummaryrefslogtreecommitdiff
path: root/find_all_good_strings.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-09-11 09:08:58 -0600
committerJack Sangdahl <[email protected]>2025-09-11 09:08:58 -0600
commit144aefa71917d45782ac4673a934b3b4e7523413 (patch)
tree0417527451d1dcccccdf2eba0c4a0e87a5e9f03f /find_all_good_strings.c
parent2769f3100712f1dc4f8c27181fc2c1f98fc3352c (diff)
downloadleetcode-144aefa71917d45782ac4673a934b3b4e7523413.tar.gz
leetcode-144aefa71917d45782ac4673a934b3b4e7523413.zip
1397. find all good strings
Diffstat (limited to 'find_all_good_strings.c')
-rw-r--r--find_all_good_strings.c80
1 files changed, 80 insertions, 0 deletions
diff --git a/find_all_good_strings.c b/find_all_good_strings.c
new file mode 100644
index 0000000..7190c0f
--- /dev/null
+++ b/find_all_good_strings.c
@@ -0,0 +1,80 @@
+// 1397. Find All Good Strings
+#include "leetcode.h"
+
+/*
+ * given the strings 's1' and 's2' of size 'n' and the string 'evil', return the
+ * number of good strings. a good string has size 'n', it is alphabetically
+ * greater than or equal to 's1', it is alphabetically smaller or less than
+ * 's2', and it does not contain the string 'evil' as a substring. since the
+ * answer can be a huge number, return this modulo 10^9+7.
+ */
+
+static int mod = 1e9 + 7;
+
+int count_good_strings(char *s, int n, char *evil, int m, long long *dp) {
+ int sum = 0, i, k;
+ for (i = 0; i <= n - m; ++i) {
+ for (k = 0; k < m && s[i + k] == evil[k]; ++k)
+ ;
+ if (k == m) {
+ for (int j = i + k - 1; j >= i; --j) {
+ sum += (s[j] - 'a') * dp[n - j - 1];
+ sum %= mod;
+ }
+ return sum - 1;
+ }
+ if (s[i + k] < evil[k])
+ sum += (s[i] - 'a') * dp[n - i - 1];
+ else
+ sum += dp[n - i] - ('z' + 1 - s[i]) * dp[n - i - 1];
+ sum %= mod;
+ }
+ for (; i < n; ++i) {
+ sum += (s[i] - 'a') * dp[n - i - 1];
+ sum %= mod;
+ }
+ return sum;
+}
+
+int findGoodStrings(int n, char *s1, char *s2, char *evil) {
+ int m = strlen(evil), k = 0, i = 1;
+ long long *dp = (long long *)malloc((n + 1) * sizeof(long long));
+ memset(dp, 0, m * sizeof(long long));
+ while (i < m) {
+ if (evil[k] == evil[i])
+ dp[i++] = ++k;
+ else if (k > 0)
+ k = dp[k - 1];
+ else
+ ++i;
+ }
+ k = m - dp[m - 1];
+ dp[0] = 1LL;
+ for (i = 1; i < m; ++i)
+ dp[i] = (dp[i - 1] * 26LL) % mod;
+ for (; i <= n; ++i) {
+ if (k == m) {
+ dp[i] = (dp[i - 1] * 26LL) % mod;
+ dp[i] -= dp[i - m];
+ } else {
+ dp[i] = ((dp[i - 1] + dp[i - k - 1]) * 26LL) % mod;
+ dp[i] -= dp[i - m] + dp[i - k];
+ }
+ }
+ int ans = count_good_strings(s2, n, evil, m, dp) -
+ count_good_strings(s1, n, evil, m, dp);
+ if (!strstr(s1, evil))
+ ans++;
+ if (ans < 0)
+ ans += mod;
+ return ans % mod;
+}
+
+int main() {
+ char *s11 = "aa", *s21 = "da", *e1 = "b";
+ char *s12 = "leetcode", *s22 = "leetgoes", *e2 = "leet";
+ char *s13 = "gx", *s23 = "gz", *e3 = "x";
+ printf("%d\n", findGoodStrings(2, s11, s21, e1)); // expect: 51
+ printf("%d\n", findGoodStrings(8, s12, s22, e2)); // expect: 0
+ printf("%d\n", findGoodStrings(2, s13, s23, e3)); // expect: 2
+}