数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学至少包含前K个字母一次的子串计数
在这个问题中，我们需要计算包含至少一个所有K个字符的子串。
在这里，我们将使用两种不同的方法来解决这个问题。第一种方法获取给定字符串的所有子串，检查子串是否包含所有K个字符，并计算包含所有K个字符的子串。
第二种方法使用滑动窗口技术来解决这个问题。
问题陈述 - 我们给定一个包含N个字符的字符串alpha。此外，我们还给定K，表示包含多个仅前K个字母字符的字符串。我们需要计算包含所有K个字符至少出现一次的子串总数。
示例
输入
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 - 将'result'初始化为0，以存储有效子串的计数。
步骤5 - 开始遍历子串列表，并定义'freq'映射以存储当前字符串中字符的频率。还将'chars'初始化为0，以计算字符串中不同的字符。
步骤6 - 开始遍历当前字符串。如果映射中字符的频率为0，则更新频率并将'chars'值加1。
步骤7 - 如果chars的值等于K，则将'result'加1。
步骤8 - 返回result值。
示例
#include <bits/stdc++.h>
using namespace std;
int numberOfSubstrings(string alpha, int K) {
// Finding all substrings of the alpha
vector<string> subStr;
for (int p = 0; p < alpha.size(); p++) {
for (int q = 1; q <= alpha.size() - p; q++) {
// Get substring from p to q
subStr.push_back(alpha.substr(p, q));
}
}
// Counting the number of substrings containing all K characters
int result = 0;
for (int p = 0; p < subStr.size(); p++) {
// To store the frequency of characters in the current substring
map<char, int> freq;
// To store the totally different characters
int chars = 0;
// Traverse substring
for (int q = 0; q < subStr[p].size(); q++) {
// If a character does not exist in the map, increment chars
if (freq[subStr[p][q]] == 0) {
freq[subStr[p][q]]++;
chars++;
}
}
// If different chars are the same as K, the string is valid.
if (chars == K) {
result++;
}
}
return result;
}
int main() {
string alpha = "abcdda";
int K = 4;
cout << "The number of substrings containing all K characters at least once is " << numberOfSubstrings(alpha, K);
return 0;
}
输出
The number of substrings containing all K characters at least once is 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 - 在嵌套循环中递增'left'指针。
步骤4.5 - 在主循环中递增'right'指针。
步骤5 - 否则，递增'right'指针值。
步骤6 - 返回'cnt'值。
示例
让我们通过示例输入了解滑动窗口技术如何解决问题。
输入 - 'abcdaabc'，K = 4
第一个窗口将是'abcd'，包含所有4个字符。因此，我们可以说(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) {
// For storing the frequency of characters
unordered_map<char, int> freq;
int left = 0, right = 0, len = alpha.size(), cnt = 0;
// Traveres the string
while (right < len) {
// Update character frequency
freq[alpha[right]]++;
// If the size of the map contains all K characters
if (freq.size() == K) {
// Traverse the map until the map size is k
while (freq.size() == K) {
// Add all valid substrings.
// If (left, right) contains all K characters, (left, right + 1), (left + right + 2), ... also contains.
cnt += len - right;
// Update character frequency
freq[alpha[left]]--;
// Remove the character if its frequency is 0.
if (freq[alpha[left]] == 0)
freq.erase(alpha[left]);
// Move to the next character from left
left++;
}
// Increment the right pointer.
right++;
}
// Increment right by 1
else {
right++;
}
}
// Return the value of cnt
return cnt;
}
int main() {
string alpha = "abcdda";
int K = 4;
cout << "The number of substrings containing all K characters at least once is " << numberOfSubstrings(alpha, K);
return 0;
}
输出
The number of substrings containing all K characters at least once is 4
时间复杂度 - O(N)，用于滑动窗口。
空间复杂度 - O(K)，用于在映射中存储频率。
程序员也可以使用数组来存储字符的频率而不是映射，因为我们可以比映射更快地访问数组中的元素。为了进行更多练习，程序员尝试解决我们需要计算仅包含所有K个字符一次的字符串数量的问题。
93 次浏览
