aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-07-25 11:35:11 -0600
committerJack Sangdahl <[email protected]>2025-07-25 11:35:11 -0600
commite33f4b8c11864d8acd77307e4a104eaf765b71d0 (patch)
tree6aeafb7a35af6261d5e7d00f6dedf8525b52748a
parentbd21c48fbf4b27bd203b5788b03735f575294df0 (diff)
downloadleetcode-e33f4b8c11864d8acd77307e4a104eaf765b71d0.tar.gz
leetcode-e33f4b8c11864d8acd77307e4a104eaf765b71d0.zip
3298. count substrings that can be rearranged to contain a string 2
-rw-r--r--count_substr_rearr_cont_str2.c53
-rw-r--r--count_substr_rearr_cont_str2.py37
2 files changed, 90 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
+}
diff --git a/count_substr_rearr_cont_str2.py b/count_substr_rearr_cont_str2.py
new file mode 100644
index 0000000..f1b5754
--- /dev/null
+++ b/count_substr_rearr_cont_str2.py
@@ -0,0 +1,37 @@
+# 3298. Count Substrings That Can Be Rearranged to Contain a String II
+from collections import Counter
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def validSubstringCount(self, word1, word2):
+ """
+ :type word1: str
+ :type word2: str
+ :rtype: int
+ """
+ cnt = Counter(word2)
+ k, ans, i = len(word2), 0, 0
+ for j, c in enumerate(word1):
+ if cnt[c] > 0:
+ k -= 1
+ cnt[c] -= 1
+ while k == 0 and cnt[word1[i]] < 0:
+ cnt[word1[i]] += 1
+ i += 1
+ ans += 0 if k else i + 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.validSubstringCount(word1="bcca", word2="abc"))
+ print(obj.validSubstringCount(word1="abcabc", word2="abc"))
+ print(obj.validSubstringCount(word1="abcabc", word2="aaabc"))