计算至少出现一次前 K 个字母的子字符串
在此问题中，我们需要计算至少出现 1 次所有 K 个字符的子字符串。
在这里，我们将使用两种不同的方法来解决这个问题。第一种方法取给定字符串的所有子字符串，检查子字符串是否包含所有 K 个字符，并计算包含所有 K 个字符的子字符串。
第二种方法使用滑动窗口技术来解决问题。
问题陈述 - 我们给出了一个包含 N 个字符的字符串 alpha。此外，我们给出了 K，表示仅包含前 K 个字母字符多次出现的字符串。我们需要计算包含所有 K 个字符至少 1 次出现的子字符串总数。
示例
输入
alpha = "abcdda", K = 4;
输出
4
说明- 包含所有 4 个字符的子字符串为 'abcd'、'abcdd'、'abcdda' 和 'bcdda'。
输入
alpha = "abc", K = 5
输出
0
解释- 给定字符串中没有包含所有 5 个字符的子字符串。
输入
alpha = "ccbba"; K = 3;
输出
2
解释- 字符串"ccbba"和"cbba"包含所有 3 个字符。
方法 1
在此方法中，我们将遍历字符串以获取所有子字符串并将它们存储在列表中。之后，我们将从字符串列表中计算至少包含一次所有 K 个字符的字符串的数量。
算法
步骤 1 - 初始化"subStr"列表以存储所有子字符串。
步骤 2 - 开始遍历字符串。此外，使用嵌套循环从 1 到字符串大小 - p 进行迭代。
步骤 3 - 使用 substr() 方法从第 p 个索引获取长度等于 q 的子字符串。另外，将子字符串推送到"subStr"列表。
步骤 4- 用 0 初始化"result"以存储有效子字符串的数量。
步骤 5 - 开始遍历子字符串列表，并定义"freq"映射以存储当前字符串中字符的频率。另外，用 0 初始化"chars"以计算字符串中的不同字符。
步骤 6 - 开始遍历当前字符串。如果字符在映射中的频率为 0，则更新频率，并将"chars"值增加 1。
步骤 7 - 如果 chars 的值等于 K，则将"result"增加 1。
步骤 8 - 返回结果值。
示例
#include <bits/stdc++.h>
using namespace std;
int numberOfSubstrings(string alpha, int K) {
// 查找 alpha 的所有子字符串
vector<string> subStr;
for (int p = 0; p < alpha.size(); p++) {
for (int q = 1; q <= alpha.size() - p; q++) {
// 获取从 p 到 q 的子字符串
subStr.push_back(alpha.substr(p, q));
}
}
// 计算包含所有 K 个字符的子字符串的数量
int result = 0;
for (int p = 0; p < subStr.size(); p++) {
// 存储当前子字符串中字符的频率
map<char, int> freq;
// 存储完全不同的字符
int chars = 0;
// 遍历子字符串
for (int q = 0; q < subStr[p].size(); q++) {
// 如果字符在映射中不存在，则增加字符数
if (freq[subStr[p][q]] == 0) {
freq[subStr[p][q]]++;
chars++;
}
}
// 如果不同的字符与 K 相同，则字符串有效。
if (chars == K) {
result++;
}
}
return result;
}
int main() {
string alpha = "abcdda";
int K = 4;
cout << "至少包含所有 K 个字符一次的子字符串的数量为 " << numberOfSubstrings(alpha, K);
return 0;
}
输出
至少包含一次所有 K 个字符的子字符串的数量为 4
时间复杂度 - O(N*N*M)，其中 O(N*N) 是获取所有子字符串，O(M) 是遍历字符串。
空间复杂度 - O(N*N) 存储所有子字符串。
方法 2
在这种方法中，我们将使用滑动窗口技术来计算至少包含一次所有 K 个字符的子字符串的数量。
算法
步骤 1 - 初始化 'freq' 映射以存储字符频率，'left' 和 'right' 指针为 0，表示滑动窗口指针，'len' 为字符串长度，'cnt' 为 0存储字符串的数量。
步骤 2 - 进行迭代，直到"right"小于字符串长度。
步骤 3 - 增加映射中"right"索引处的字符的字符频率。
步骤 4 - 如果映射的大小等于 K，则意味着我们得到了包含所有 K 个字符的子字符串。因此，请遵循以下步骤。
步骤 4.1 - 进行迭代，直到映射的大小等于 K。
步骤 4.2 - 将"len - right"添加到"cnt"。
步骤 4.3 - 要从当前窗口中删除左侧字符，请减少其在映射中的频率。如果映射中字符的频率为 0，则从映射中删除该字符。
步骤 4.4- 在嵌套循环中增加"左"指针。
步骤 4.5 - 在主循环中增加"右"指针。
步骤 5 - 否则，增加"右"指针值。
步骤 6 - 返回"cnt"值。
示例
让我们通过示例输入了解滑动窗口技术如何解决问题。
输入 - "abcdaabc"，K = 4
第一个窗口将是包含所有 4 个字符的"abcd"。因此，我们可以说 (0, 3)、(0, 4)、(0, 5)、(0, 6) 和 (0, 7) 所有子字符串都包含所有 K 个字符。
之后，从 1 到 4 的下一个窗口包含所有字符。因此，(1, 4)、(1,5)、(1, 6) 和 (1, 7) 所有子字符串都至少包含一次所有 K 个字符。
这样，我们可以计算每个有效窗口的子字符串数量。
#include <bits/stdc++.h>
using namespace std;
int numberOfSubstrings(string alpha, int K) {
// 用于存储字符的频率
unordered_map<char, int> freq;
int left = 0, right = 0, len = alpha.size(), cnt = 0;
// 遍历字符串
while (right < len) {
// 更新字符频率
freq[alpha[right]]++;
// 如果映射的大小包含所有 K 个字符
if (freq.size() == K) {
// 遍历映射，直到映射大小为 k
while (freq.size() == K) {
// 添加所有有效子字符串。
// 如果 (left, right) 包含所有 K 个字符，则 (left, right + 1)、(left + right + 2)，... 也包含。
cnt += len - right;
// 更新字符频率
freq[alpha[left]]--;
// 如果字符出现频率为 0，则删除该字符。
if (freq[alpha[left]] == 0)
freq.erase(alpha[left]);
// 从左侧移动到下一个字符
left++;
}
// 增加右指针。
right++;
}
// 将右指针增加 1
else {
right++;
}
}
// 返回 cnt 的值
return cnt;
}
int main() {
string alpha = "abcdda";
int K = 4;
cout << "至少包含所有 K 个字符一次的子字符串的数量为 " << numberOfSubstrings(alpha, K);
return 0;
}
输出
至少包含一次所有 K 个字符的子字符串的数量为 4
时间复杂度 - O(N)，用于滑动窗口。
空间复杂度 - O(K)，用于将频率存储在映射中。
程序员还可以使用数组来存储字符的频率，而不是使用映射，因为我们可以从数组中访问元素的时间比使用映射要短。为了进行更多练习，程序员尝试解决需要计算仅包含一次所有 K 个字符的字符串数量的问题。
