LeetCode 3297.统计重新排列后包含另一个字符串的子字符串数目 I：滑动窗口

【LetMeFly】3297.统计重新排列后包含另一个字符串的子字符串数目 I：滑动窗口

力扣题目链接：https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-i/

给你两个字符串 word1 和 word2 。

如果一个字符串 x 重新排列后，word2 是重排字符串的前缀，那么我们称字符串 x 是 合法的 。

请你返回 word1 中合法子字符串的数目。

示例 1：

输入：word1 = "bcca", word2 = "abc"

输出：1

解释：

唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。

示例 2：

输入：word1 = "abcabc", word2 = "abc"

输出：10

解释：

除了长度为 1 和 2 的所有子字符串都是合法的。

示例 3：

输入：word1 = "abcabc", word2 = "aaabc"

输出：0

解释：

1 <= word1.length <= 10⁵
1 <= word2.length <= 10⁴
word1 和 word2 都只包含小写英文字母。

解题方法：滑动窗口

首先统计word2中每个字符分别出现了多少次，接着开始滑动窗口：

窗口起点是word1的每个字符，窗口终点是第一次“合法”的最小结束位置。

对于一个起点l，若最小合法位置是r，则合法方案是[l, r]、[l, r + 1]、...、[l, len(word1) - 1]。

时间复杂度 $O(len(word1)\times C+len(word2))$ ，其中 $C = 26$
空间复杂度 $O (C)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-01-09 11:03:16* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-09 12:39:10*/
typedef long long ll;
class Solution {
private:bool ok(int* cnt1, int* cnt2) {for (int i = 0; i < 26; i++) {if (cnt1[i] < cnt2[i]) {return false;}}return true;}
public:ll validSubstringCount(string& word1, string& word2) {int cnt1[26] = {0}, cnt2[26] = {0};for (char c : word2) {cnt2[c - 'a']++;}ll ans = 0;for (int l = 0, r = 0; l < word1.size(); l++, r = max(r, l)) {if (l) {cnt1[word1[l - 1] - 'a']--;}while (!ok(cnt1, cnt2)) {if (r == word1.size()) {return ans;}cnt1[word1[r++] - 'a']++;}ans += word1.size() - r + 1;}return ans;}
};#ifdef _WIN32
/*
bcca
abc1
*/
/*
abcabc
abc10
*/
int main() {Solution sol;string a, b;while (cin >> a >> b) {cout << sol.validSubstringCount(a, b) << endl;}return 0;
}
#endif

Python

'''
Author: LetMeFly
Date: 2025-01-09 12:39:58
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-09 12:44:30
'''
from collections import Counter, defaultdictclass Solution:def ok(self, cnt1: defaultdict) -> bool:for k, v in self.cnt2.items():if cnt1[k] < v:return Falsereturn Truedef validSubstringCount(self, word1: str, word2: str) -> int:self.cnt2 = Counter(word2)cnt1 = defaultdict(int)ans = l = r = 0while l < len(word1):if l:cnt1[word1[l - 1]] -= 1while not self.ok(cnt1):if r == len(word1):return anscnt1[word1[r]] += 1r += 1ans += len(word1) - r + 1l += 1return ans

Java

/** @Author: LetMeFly* @Date: 2025-01-09 12:46:14* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-09 12:51:13*/
class Solution {private boolean ok(int[] a, int[] b) {for (int i = 0; i < 26; i++) {if (a[i] < b[i]) {return false;}}return true;}public long validSubstringCount(String word1, String word2) {int[] cnt1 = new int[26], cnt2 = new int[26];for (char c : word2.toCharArray()) {cnt2[c - 'a']++;}long ans = 0;for (int l = 0, r = 0; l < word1.length(); l++) {if (l > 0) {cnt1[word1.charAt(l - 1) - 'a']--;}while (!ok(cnt1, cnt2)) {if (r == word1.length()) {return ans;}cnt1[word1.charAt(r++) - 'a']++;}ans += word1.length() - r + 1;}return ans;}
}

Go

/** @Author: LetMeFly* @Date: 2025-01-09 12:52:14* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-09 13:10:20*/
package main// import "fmt"func ok(a, b []int) bool {for i := range a {if a[i] < b[i] {return false}}return true
}func validSubstringCount(word1 string, word2 string) (ans int64) {cnt1, cnt2 := make([]int, 26), make([]int, 26)for _, c := range word2 {cnt2[c - 'a']++}// fmt.Println(cnt2)for l, r := 0, 0; l < len(word1); l++ {if l > 0 {cnt1[word1[l - 1] - 'a']--}for !ok(cnt1, cnt2) {if r == len(word1) {return}cnt1[word1[r] - 'a']++r++}// fmt.Println(cnt1)// fmt.Println(r)ans += int64(len(word1) - r + 1)}return
}