计算C ++中恰好有k个不同字符的子字符串数

  • Z时代
  • 2024-01-10
  • 分类：综合

给定一个仅包含小写字母和整数值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(string str, int length, int k) 接受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

以上是 计算C ++中恰好有k个不同字符的子字符串数 的全部内容， 来源链接： utcz.com/z/348721.html

回到顶部