JZX轻语：简
LeetCode 3296 & 3297 - 统计重新排列后包含另一个字符串的子字符串数目
发表于2025年01月10日
典型滑动窗口题目，统计word2的字符出现频次，以及word1当前窗口的字符出现频次，如果word1当前窗口每个字符的出现频次均大于等于word2的频次，则说明可以通过重新排列word1的滑动窗口内的字串得到word2，以及固定窗口左侧，一直延伸到word1的末尾的所有子串都满足题目要求。
II属于困难题，上述的做法会超时。改进点可以使用一个变量diff记录word1当前窗口还需要多少个字符才能通过重新排列得到word2，然后在滑动窗口的过程中，根据diff的值来判断是否需要移动窗口左侧或者右侧。diff值可以在窗口变化时更新，判断当前滑走/滑入的字符是否会影响diff的值来采取递增或者递减。
第一题做法：
class Solution {
public:
auto count(const string& word, int left, int right) {
vector<int> _res(26, 0);
for (int i = left; i < right; ++i) _res[word[i] - 'a']++;
return _res;
};
auto match(const vector<int> &cur_word1_sub_cnt, const vector<int> &word2_cnt) {
for (int i = 0; i < 26; ++i) if (cur_word1_sub_cnt[i] < word2_cnt[i]) return false;
return true;
}
long long validSubstringCount(string word1, string word2) {
if (word1.size() < word2.size()) return 0;
long long ans = 0;
auto word2_cnt = count(word2, 0, word2.size());
auto cur_word1_sub_cnt = count(word1, 0, word2.size());
int left = 0, right = word2.size() - 1;
while (right < word1.size()) {
if (match(cur_word1_sub_cnt, word2_cnt)) {
ans += word1.size() - right;
--cur_word1_sub_cnt[word1[left++] - 'a'];
} else {
++right;
if (right < word1.size())
++cur_word1_sub_cnt[word1[right] - 'a'];
}
}
return ans;
}
};第二题的做法：
class Solution {
public:
auto count(const string& word, int left, int right) {
vector<int> _res(26, 0);
for (int i = left; i < right; ++i) _res[word[i] - 'a']++;
return _res;
};
long long validSubstringCount(string word1, string word2) {
if (word1.size() < word2.size()) return 0;
long long ans = 0;
auto word2_cnt = count(word2, 0, word2.size());
auto cur_word1_sub_cnt = count(word1, 0, word2.size());
int diff = 0;
// diff表示word1当前窗口还需要多少个字符才能通过重新排列得到word2
// 注意如果word1当前窗口的某个字符出现次数超过word2的次数，不需要减去， 说明已经满足了
for (int i = 0; i < 26; ++i) diff += max(0, word2_cnt[i] - cur_word1_sub_cnt[i]);
int left = 0, right = word2.size() - 1;
while (right < word1.size()) {
if (diff == 0) {
ans += word1.size() - right;
--cur_word1_sub_cnt[word1[left] - 'a'];
// 如果减去后的该字符次数小于word2的次数，说明需要增加diff
// 如果仍然大于等于word2的次数，说明还是处于满足状态，不需要增加diff
if (cur_word1_sub_cnt[word1[left] - 'a'] < word2_cnt[word1[left] - 'a']) ++diff;
++left;
} else {
++right;
if (right < word1.size()) {
++cur_word1_sub_cnt[word1[right] - 'a'];
// 同理
if (cur_word1_sub_cnt[word1[right] - 'a'] <= word2_cnt[word1[right] - 'a']) --diff;
}
}
}
return ans;
}
};