diff options
author | Jack Sangdahl <[email protected]> | 2025-07-25 11:35:11 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-07-25 11:35:11 -0600 |
commit | e33f4b8c11864d8acd77307e4a104eaf765b71d0 (patch) | |
tree | 6aeafb7a35af6261d5e7d00f6dedf8525b52748a | |
parent | bd21c48fbf4b27bd203b5788b03735f575294df0 (diff) | |
download | leetcode-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.c | 53 | ||||
-rw-r--r-- | count_substr_rearr_cont_str2.py | 37 |
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")) |