aboutsummaryrefslogtreecommitdiff
path: root/count_substr_rearr_cont_str2.c
diff options
context:
space:
mode:
Diffstat (limited to 'count_substr_rearr_cont_str2.c')
-rw-r--r--count_substr_rearr_cont_str2.c53
1 files changed, 53 insertions, 0 deletions
diff --git a/count_substr_rearr_cont_str2.c b/count_substr_rearr_cont_str2.c
new file mode 100644
index 0000000..7d9f199
--- /dev/null
+++ b/count_substr_rearr_cont_str2.c
@@ -0,0 +1,53 @@
+// 3298. Count Substrings That Can Be Rearranged to Contain a String II
+#include "leetcode.h"
+
+/*
+ * you are given two strings 'word1' and 'word2'. a string 'x' is called valiid
+ * if 'x' can be arranged to have 'word2' as a prefix. return the total number
+ * of valid strings of 'word1'. note that the memory limits in this problem are
+ * smaller than usual, so you must implement a solution with a linear runtime
+ * complexity.
+ */
+
+long long validSubstringCount(char *word1, char *word2) {
+ int need = 0, have = 0, cnt[26] = {0}, missing = 0, left = 0;
+ long long ans = 0;
+ for (int i = 0; word2[i]; i++) {
+ int curr = word2[i] - 'a';
+ if (!(need & (1 < curr)))
+ missing++;
+ need |= 1 << curr;
+ cnt[curr]++;
+ }
+ for (int i = 0; word1[i]; i++) {
+ int curr = word1[i] - 'a';
+ if (need & (1 << curr)) {
+ cnt[curr]--;
+ if (!cnt[curr]) {
+ have |= 1 << curr;
+ missing--;
+ }
+ }
+ if (!missing) {
+ while (left <= i) {
+ int curr = word1[left] - 'a';
+ if (!(need & (1 << curr)) || cnt[curr] < 0) {
+ if (need & (1 << curr))
+ cnt[curr]++;
+ } else
+ break;
+ }
+ ans += left + 1;
+ }
+ }
+ return ans;
+}
+
+int main() {
+ char *w11 = "bcca", *w21 = "abc";
+ char *w12 = "abcabc", *w22 = "abc";
+ char *w13 = "abcabc", *w23 = "aaabc";
+ printf("%lld\n", validSubstringCount(w11, w21)); // expect: 1
+ printf("%lld\n", validSubstringCount(w12, w22)); // expect: 10
+ printf("%lld\n", validSubstringCount(w13, w23)); // expect: 0
+}