C ++中由相同字符组成的长度为K的子字符串的最大数目

给定任务是找到由相同字符组成的长度为K的子串的最大数量。给定一个字符串s和另一个整数K,我们必须计算大小为K的具有相同字符的子字符串的出现。

从找到的子字符串中,我们必须选择出现时间最多的子字符串。

现在让我们使用示例了解我们必须做的事情-

输入值

s = ”tuuxyyuuc”, K = 2

输出结果

2

说明

在这里,长度为2且具有相同字符的子字符串为:“ uu”和“ yy”,但可以看出,“ yy”仅出现1次,“ uu”出现2次。因此,输出变为2。

输入值

s = “hhigggff”, K = 3

输出结果

1

在以下程序中使用的方法如下

  • 在Max()函数中,初始化int ans = 0以存储最终答案,size = str.size()以存储字符串的大小,并声明char c以存储我们需要检查的字符。

  • 从j = 0循环直到j <26,然后将c ='a'+ j放入,因为我们将检查每个字符。

  • 初始化变量int CurrCh = 0,用于存储包含当前字符的子数组的出现。

  • 从i = 0循环直到i <= size – K,然后检查(str [i]!= c)。如果是这样,则添加继续;否则,请继续。声明。

  • 初始化count = 0以存储当前字符的子数组的长度。

  • 创建一个条件为(i <size && count!= K && str [i] == c)的while循环,并在循环内递增i和count。在while循环外,将i减1。

  • 检查是否(计数== K)。如果是这样,则增加CurrCh

  • 关闭第二个For循环,并通过放置ans = max(ans,CurrCh)来更新ans的值。

  • 最后关闭第一个For循环并返回ans

示例

#include <bits/stdc++.h>
using namespace std;
int Max(string str, int K){
   int ans = 0, size = str.size();
   char c;
   //Checking for all characters
   for (int j = 0; j < 26; j++){
      c = 'a' + j;
      //checking for current character
      int CurrCh = 0;
      for (int i = 0; i <= size - K; i++){
         if (str[i] != c)
            continue;
         //Counting the size of sub-string
         int count = 0;
         while (i < size && count != K && str[i] == c){
            i++;
            count++;
         }
         i--;
         //Increment CurrCh if sub-string has length K
         if (count == K)
            CurrCh++;
      }
      //Update ans
      ans = max(ans, CurrCh);
   }
   return ans;
}
//main function
int main(){
   string str = "tuuuxyuuu";
   int K = 3;
   cout << Max(str, K);
   return 0;
}

输出结果

2