数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中统计具有精确 k 个不同字符的子字符串数量
给定一个仅包含小写字母的字符串 str[] 和一个整数 k。目标是找到 str 的所有可能的子字符串中，具有恰好 k 个不同元素的子字符串的数量。
例如
输入
str= ”pqr” k=2
输出
Count of number of substrings with exactly k distinct characters are: 2
解释
The substrings having exactly 2 distinct elements are: “pq”, “qr”.
输入
str= ”stristr” k=4
输出
Count of number of substrings with exactly k distinct characters are: 10
解释
The substrings having exactly 2 distinct elements are: “stri”, “tris”, “rist”, “istr”, “stris”, “trist”, “ristr”, “strist”, “tristr”, “stristr”.
下面程序中使用的方案如下 −
在这种方法中，我们将使用一个数组 array[26] 来存储字符串 str 中英文字母的频率。现在使用两个 for 循环遍历 str，如果对于子字符串，每个字符只出现一次，则递增唯一字符的数量，在该子字符串的末尾，如果该数量等于 k，则根据给定条件递增子字符串的数量。
将字符串 str 作为输入。
获取一个具有正值的整数 k。
函数 substring_k(string str, int length, int k) 获取 str 和 k 并返回具有恰好 k 个不同字符的子字符串的数量。
将初始计数设置为 0。
获取频率数组 array[26]。
使用两个 for 循环从 i=0 到 i<length 和 j=i 到 j<length 遍历 str。
将 temp 作为子字符串 str[i 到 j] 中唯一元素的数量。
如果 array[str[j] - 'a'] == 0，则表示此字符 str[j] 在此子字符串中第一次出现。因此，递增 temp。
现在使用 array[str[j] - 'a']++ 递增当前字符的数量。
如果 temp 等于 k，则递增计数。
如果 temp 大于 k，则停止进一步计算并中断循环。
在所有循环结束时，返回计数作为结果。
示例
#include<bits/stdc++.h>
using namespace std;
int substring_k(string str, int length, int k){
int count = 0;
int array[26];
for (int i = 0; i < length; i++){
int temp = 0;
memset(array, 0, sizeof(array));
for (int j = i; j < length; j++){
if(array[str[j] − 'a'] == 0){
temp++;
}
array[str[j] − 'a']++;
if (temp == k){
count++;
}
if(temp > k){
break;
}
}
}
return count;
}
int main(){
string str = "abc";
int length = str.length();
int k = 1;
cout<<"Count of number of substrings with exactly k distinct characters are: "<<substring_k(str, length, k);
return 0;
}输出
如果我们运行上述代码，它将生成以下输出：
Count of number of substrings with exactly k distinct characters are: 3
更新于: 2021年1月5日
1K+ 次浏览
广告