문자열 str이 주어집니다. 목표는 각 문자가 최대 k 번 발생하는 str 의 부분 문자열 수를 계산하는 것입니다. 예를 들어 입력이 "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[길이-1] ). 참이면 1을 반환합니다.
-
함수 check_Start_End(string str, int length)는 str과 그 길이를 입력으로 받아 같은 문자로 시작하고 끝나는 str의 부분 문자열 개수를 반환합니다.
-
초기 카운트를 0으로 합니다.
-
두 개의 for 루프를 사용하여 str을 탐색합니다. i=0에서 i<길이 및 내부 j=1에서 j=length-1까지.
-
모든 길이의 substr(i,j)를 사용하여 모든 부분 문자열을 얻습니다. 각 부분 문자열을 check()에 전달하십시오. 1을 반환하면 count를 증가시킵니다.
-
두 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