计算在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（string str）接受子字符串str，并检查它的第一个字符和最后一个字符是否相同。（str [0] == str [length-1]）。如果为true，则返回1。

  • 函数check_Start_End（string str，int length）以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
计算在C ++中以字符X开头并以字符Y结尾的子字符串 计算C ++中首尾相同的子字符串
相关笔记