class Solution {
public:
long long validSubstringCount(string word1, string word2) {
}
};
3298. 统计重新排列后包含另一个字符串的子字符串数目 II
给你两个字符串 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 <= 1061 <= word2.length <= 104word1 和 word2 都只包含小写英文字母。相似题目
原站题解
python3 解法, 执行用时: 1742 ms, 内存消耗: 23.2 MB, 提交时间: 2024-10-13 23:35:54
class Solution:
def validSubstringCount(self, s: str, t: str) -> int:
if len(s) < len(t):
return 0
# t 的字母出现次数与 s 的字母出现次数之差
cnt = defaultdict(int) # 也可以用 Counter(t)，但是会慢很多
for b in t:
cnt[b] += 1
# 窗口内有 less 个字母的出现次数比 t 的少
less = len(cnt)
ans = left = 0
for b in s:
cnt[b] -= 1
if cnt[b] == 0:
# 窗口内 b 的出现次数和 t 一样
less -= 1
while less == 0: # 窗口符合要求
if cnt[s[left]] == 0:
# s[left] 移出窗口之前，检查出现次数，
# 如果窗口内 s[left] 的出现次数和 t 一样，
# 那么 s[left] 移出窗口后，窗口内 s[left] 的出现次数比 t 的少
less += 1
cnt[s[left]] += 1
left += 1
ans += left
return ans
golang 解法, 执行用时: 66 ms, 内存消耗: 7.9 MB, 提交时间: 2024-10-13 23:35:27
func validSubstringCount(s, t string) (ans int64) {
if len(s) < len(t) {
return 0
}
cnt := [26]int{} // t 的字母出现次数与 s 的字母出现次数之差
for _, b := range t {
cnt[b-'a']++
}
less := 0 // 统计窗口内有多少个字母的出现次数比 t 的少
for _, c := range cnt {
if c > 0 {
less++
}
}
left := 0
for _, b := range s {
cnt[b-'a']--
if cnt[b-'a'] == 0 {
// 窗口内 b 的出现次数和 t 一样
less--
}
for less == 0 { // 窗口符合要求
if cnt[s[left]-'a'] == 0 {
// s[left] 移出窗口之前，检查出现次数，
// 如果窗口内 s[left] 的出现次数和 t 一样，
// 那么 s[left] 移出窗口后，窗口内 s[left] 的出现次数比 t 的少
less++
}
cnt[s[left]-'a']++
left++
}
ans += int64(left)
}
return
}
cpp 解法, 执行用时: 203 ms, 内存消耗: 49.6 MB, 提交时间: 2024-10-13 23:34:49
class Solution {
public:
long long validSubstringCount(string s, string t) {
if (s.length() < t.length()) {
return 0;
}
int cnt[26]{}; // t 的字母出现次数与 s 的字母出现次数之差
for (char b : t) {
cnt[b - 'a']++;
}
int less = 0; // 统计窗口内有多少个字母的出现次数比 t 的少
for (int c : cnt) {
if (c > 0) {
less++;
}
}
long long ans = 0;
int left = 0;
for (char b : s) {
cnt[b - 'a']--;
if (cnt[b - 'a'] == 0) {
// b 移入窗口后，窗口内 b 的出现次数和 t 一样
less--;
}
while (less == 0) { // 窗口符合要求
char out_char = s[left++]; // 准备移出窗口的字母
if (cnt[out_char - 'a'] == 0) {
// out_char 移出窗口之前，检查出现次数，
// 如果窗口内 out_char 的出现次数和 t 一样，
// 那么 out_char 移出窗口后，窗口内 out_char 的出现次数比 t 的少
less++;
}
cnt[out_char - 'a']++;
}
ans += left;
}
return ans;
}
};
java 解法, 执行用时: 38 ms, 内存消耗: 54.8 MB, 提交时间: 2024-10-13 23:34:24
class Solution {
public long validSubstringCount(String S, String T) {
if (S.length() < T.length()) {
return 0;
}
char[] s = S.toCharArray();
char[] t = T.toCharArray();
int[] cnt = new int[26]; // t 的字母出现次数与 s 的字母出现次数之差
for (char b : t) {
cnt[b - 'a']++;
}
int less = 0; // 统计窗口内有多少个字母的出现次数比 t 的少
for (int c : cnt) {
if (c > 0) {
less++;
}
}
long ans = 0;
int left = 0;
for (char b : s) {
cnt[b - 'a']--;
if (cnt[b - 'a'] == 0) {
// b 移入窗口后，窗口内 b 的出现次数和 t 一样
less--;
}
while (less == 0) { // 窗口符合要求
char outChar = s[left++]; // 准备移出窗口的字母
if (cnt[outChar - 'a'] == 0) {
// outChar 移出窗口之前检查出现次数，
// 如果窗口内 outChar 的出现次数和 t 一样，
// 那么 outChar 移出窗口后，窗口内 outChar 的出现次数比 t 的少
less++;
}
cnt[outChar - 'a']++;
}
ans += left;
}
return ans;
}
}