计算C ++中恰好有k个不同字符的子字符串数
给定一个仅包含小写字母和整数值k的字符串str[]。目的是找到具有恰好k个不同元素的str可能的子字符串的数量。
例如
输入值
str= ”pqr” k=2输出结果
具有恰好k个不同字符的子字符串的数量计数为： 2
说明
The substrings having exactly 2 distinct elements are: “pq”, “qr”.
输入值
str= ”stristr” k=4输出结果
具有恰好k个不同字符的子字符串的数量计数为： 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(stringstr,intlength,intk)接受str和k并返回具有正好k个不同字符的子字符串数的计数。
将初始计数设为0。
以频率阵列[26]为例。
使用两个从i=0到i<lenght和j=i到j<lenght的for循环遍历str。
将temp作为子字符串str[i至j]中唯一元素的计数。
如果array[str[j]-'a']==0，则此字符str[j]首次出现在此子字符串中。因此增加温度。
现在使用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<<"具有恰好k个不同字符的子字符串的数量计数为： "<<substring_k(str, length, k);
return 0;
}输出结果如果我们运行上面的代码，它将生成以下输出-
具有恰好k个不同字符的子字符串的数量计数为： 3