C++에서 동일한 문자로 구성된 길이가 K인 부분 문자열의 최대 개수

<시간/>

주어진 작업은 길이가 K인 부분 문자열의 최대 개수를 찾는 것입니다. 동일한 문자로 구성됩니다. 주어진 문자열 s와 다른 정수 K , 우리는 K 크기의 하위 문자열의 발생을 계산해야 합니다. 같은 문자가 있습니다.

발견된 부분 문자열 중에서 가장 많이 발생하는 부분 문자열을 선택해야 합니다.

이제 예제를 사용하여 무엇을 해야 하는지 이해합시다 -

입력

s = ”tuuxyyuuc”, K = 2

출력

설명

여기에서 길이가 2이고 동일한 문자를 갖는 하위 문자열은 "uu" 및 "yy"이지만 "yy"는 1번만 발생하고 "uu"는 2번 나타나는 것을 알 수 있습니다. 따라서 출력은 2가 됩니다.

입력

s = “hhigggff”, K = 3

출력

아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다.

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 count 증분 . while 루프 밖에서는 i를 1만큼 감소시킵니다.
(카운트 ==K)인지 확인하십시오. 그렇다면 CurrCh를 증가시키십시오. .
두 번째 For 루프를 닫고 ans 값을 업데이트합니다. ans =max(ans, CurrCh)를 입력하여.
마지막으로 첫 번째 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;
}