计算在C ++中每个字符最多出现k次的子字符串
给我们一个字符串str。目标是计算str中每个字符最多出现k次的子字符串数。例如，如果输入为“abc”且k=1，则子字符串将为“a”，“b”，“c”，“ab”，“bc”，“abc”。
让我们通过示例来理解。
输入-str=“abaefgf”
输出-第一个和最后一个字符相同的子字符串计数为＆mmius;9
说明-子字符串将是
“a”, “b”, “a”, “e” ,”f”, “g”, “f”, “aba”, “fgf”. Total 9.
输入-str=“abcdef”
输出-具有相同首尾字符的子字符串计数为：6
说明-子字符串将是-
“a” , “b” , “c”, “d”, “e” ,”f”. Total 6
以下程序中使用的方法如下
解决给定问题的方法可以有多种，即幼稚方法和有效方法。因此，让我们首先来看一下幼稚的方法。我们将把各种长度的子字符串传递给一个函数check()。如果该子字符串以相同字符开始和结束，则增加计数。
取字符串str。计算长度为str.size()。
函数check（stringstr）接受子字符串str，并检查它的第一个字符和最后一个字符是否相同。（str[0]==str[length-1]）。如果为true，则返回1。
函数check_Start_End（stringstr，intlength）以str及其长度作为输入，并返回以相同字符开头和结尾的str子字符串的计数。
将初始计数设为0。
使用两个for循环遍历str。从i=0到i<length，内部j=1到j=length-1。
我们将使用所有长度的substr(i,j)获得所有子字符串。将每个子字符串传递给check()。如果返回1，则增加计数。
在两个for循环的末尾，count都将包含许多str的子字符串，它们的起始字符和结束字符相同。
返回计数作为期望的结果。
示例
#include <bits/stdc++.h>
using namespace std;
int count_k(string str, int len, int k){
int count = 0;
int arr[26];
for (int i = 0; i < len; i++){
memset(arr, 0, sizeof(arr));
for (int j = i; j < len; j++){
arr[str[j] - 'a']++;
if (arr[str[j] - 'a'] <= k)
{ count++; }
else
{ break; }
}
}
return count;
}
int main(){
string str = "bbddehj";
int k = 1;
int length = str.length();
cout<<"Count of substrings with each character occurring at most k times are: "<<count_k(str,
length, k);
return 0;
}输出结果
如果我们运行上面的代码，它将生成以下输出-
Count of substrings with each character occurring at most k times are: 14