From 144aefa71917d45782ac4673a934b3b4e7523413 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Thu, 11 Sep 2025 09:08:58 -0600 Subject: 1397. find all good strings --- find_all_good_strings.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 80 insertions(+) create mode 100644 find_all_good_strings.c (limited to 'find_all_good_strings.c') 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 +} -- cgit v1.2.3