aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--find_all_good_strings.c80
-rw-r--r--find_all_good_strings.py83
2 files changed, 163 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
+}
diff --git a/find_all_good_strings.py b/find_all_good_strings.py
new file mode 100644
index 0000000..48b64e1
--- /dev/null
+++ b/find_all_good_strings.py
@@ -0,0 +1,83 @@
+# 1397. Find All Good Strings
+from string import ascii_lowercase
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def prefix(self, s):
+ res = [0] * len(s)
+ for i in range(1, len(s)):
+ k = res[i - 1]
+ while k > 0 and s[k] != s[i]:
+ k = res[k - 1]
+ if s[k] == s[i]:
+ k += 1
+ res[i] = k
+ return res[-1]
+
+ def crete_connections(self, evil, t):
+ k = len(evil)
+ connections = [[-1] * t for _ in range(k)]
+ conn = [[] for _ in range(k)]
+ for i in range(k):
+ for letter in self.alphabet:
+ curr = self.prefix(evil + "#" + evil[0:i] + letter)
+ if curr != k:
+ connections[i][ord(letter) - ord("a")] = curr
+ if curr != 0:
+ conn[i].append([ord(letter) - ord("a"), curr])
+ cnt = [[0] for _ in range(k)]
+ for i in range(k):
+ for j in range(1, t + 1):
+ cnt[i] += [cnt[i][-1] + (connections[i][j - 1] == 0)]
+ return cnt, conn
+
+ def find_lesser_good(self, n, k, string, m, evil):
+ dp_bord = [[0] * k for _ in range(n)]
+ dp_notd = [[0] * k for _ in range(n)]
+ dp_bord[0][0] = 1
+ for it_n in range(n - 1):
+ for it_k in range(k):
+ ord_num = ord(string[it_n + 1]) - ord("a")
+ for letter, s in self.con[it_k]:
+ dp_notd[it_n + 1][s] += dp_notd[it_n][it_k]
+ if letter < ord_num:
+ dp_notd[it_n + 1][s] += dp_bord[it_n][it_k]
+ dp_notd[it_n + 1][0] += self.con_numzero[it_k][-1] * dp_notd[it_n][it_k]
+ dp_notd[it_n + 1][0] += (
+ self.con_numzero[it_k][ord_num] * dp_bord[it_n][it_k]
+ )
+ dp_notd[it_n + 1] %= m
+ idx = self.prefix(evil + "#" + string[0 : it_n + 2])
+ if idx != k and sum(dp_bord[it_n]) != 0:
+ dp_bord[it_n + 1][idx] = 1
+ return sum(dp_bord[-1]) + sum(dp_notd[-1])
+
+ def findGoodStrings(self, n, s1, s2, evil):
+ """
+ :type n: int
+ :type s1: str
+ :type s2: str
+ :type evil: str
+ :rtype: int
+ """
+ self.alphabet = ascii_lowercase
+ m, k = 10**9 + 7, len(evil)
+ self.con_numzero, self.con = self.crete_connections(evil, len(self.alphabet))
+ ans1 = self.find_lesser_good(n + 1, k, "#" + s2, m, evil)
+ ans2 = self.find_lesser_good(n + 1, k, "#" + s1, m, evil)
+ return (ans1 - ans2 + 1 - (evil in s1)) % m
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findGoodStrings(n=2, s1="aa", s2="da", evil="b"))
+ print(obj.findGoodStrings(n=8, s1="leetcode", s2="leetgoes", evil="leet"))
+ print(obj.findGoodStrings(n=2, s1="gx", s2="gz", evil="x"))