C++에서 문자의 ASCII 값의 합이 k로 나눌 수 있는 길이가 k인 부분 문자열의 수 찾기

여기서 우리는 하나의 문자열과 다른 정수 값이 k가 주어진다고 말하는 또 다른 문제를 볼 것입니다. 문자의 ASCII 값의 합이 k로 나눌 수 있는 길이가 k인 부분 문자열의 수를 찾아야 합니다.

문자열이 "BCGABC"라고 가정합니다. 그리고 k의 값은 3입니다. 여기서 문자열 BCG는 ASCII 합계 300, ABC는 ASCII 합계 294를 가지며 둘 다 k =3으로 나눌 수 있습니다.

접근 방식은 간단합니다. 먼저 길이가 k인 첫 번째 부분 문자열의 문자의 ASCII 값을 찾아야 합니다. 슬라이딩 윈도우 기법을 사용하고 윈도우의 첫 번째 문자의 ASCII를 빼고 윈도우를 슬라이딩한 후 오는 다음 문자의 ASCII를 더해야 합니다. 합계가 k로 나눌 수 있을 때 각 단계에서 카운트를 증가시킵니다. .

예시

#include <iostream>
using namespace std;
int countKLenSubstr(string str, int k) {
   int len = str.length();
   int sum = 0;
   int count = 0 ;
   for (int i = 0; i <len; i++)
      sum += str[i] ; //ASCII sum of first substring
   if (sum % k == 0)
      count++;
   for (int i = k; i < len; i++) {
      int prev_ascii = str[i-k]; //ASCII of the first character of the window
      sum -= prev_ascii;
      sum += str[i];
      if (sum % k == 0)
         count += 1;
   }
   return count ;
}
int main() {
   string s = "BCGABC" ;
   int k = 3 ;
   cout<<"Number of substrings: " << countKLenSubstr(s, k);
}

출력

Number of substrings: 2