소문자 알파벳만 포함하고 정수 값 k를 포함하는 문자열 str[]이 제공됩니다. 목표는 정확히 k개의 고유한 요소를 가진 str의 가능한 부분 문자열의 수를 찾는 것입니다.
예를 들어
입력
str= ”pqr” k=2
출력
Count of number of substrings with exactly k distinct characters are: 2
설명
The substrings having exactly 2 distinct elements are: “pq”, “qr”.
입력
str= ”stristr” k=4
출력
Count of number of substrings with exactly k distinct characters are: 10
설명
The substrings having exactly 2 distinct elements are: “stri”, “tris”, “rist”, “istr”, “stris”, “trist”, “ristr”, “strist”, “tristr”, “stristr”.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다. -
이 접근 방식에서 우리는 string str 안에 영어 알파벳의 빈도를 저장하기 위해 array array[26]을 만들 것입니다. 이제 두 개의 for 루프를 사용하여 str을 순회합니다. 하위 문자열의 경우 각 문자가 한 번 발생한 다음 고유 문자의 개수를 증가시키고, 해당 개수가 k와 같으면 해당 하위 문자열의 끝에서 지정된 조건에 따라 하위 문자열의 개수를 증가시킵니다.
-
문자열 str을 입력으로 사용합니다.
-
양수 값을 갖는 정수 k를 취하십시오.
-
함수 substring_k(string str, int length, int k)는 str과 k를 취하고 정확히 k개의 고유한 문자가 있는 부분 문자열의 수를 반환합니다.
-
초기 카운트를 0으로 합니다.
-
주파수 배열 배열[26]을 가져옵니다.
-
i=0에서 i
까지 두 개의 for 루프를 사용하여 str을 탐색합니다. -
temp를 하위 문자열 str[i to j]의 고유 요소 수로 취합니다.
-
array[str[j] − 'a']==0이면 이 문자 str[j]가 이 하위 문자열에서 처음 발생했습니다. 따라서 온도를 높이십시오.
-
이제 array[str[j] − 'a']++를 사용하여 현재 문자의 개수를 증가시킵니다.
-
temp가 k와 같으면 카운트를 증가시킵니다.
-
온도가 k보다 높으면 더 이상 통근을 중지하고 루프를 끊습니다.
-
모든 루프가 끝나면 결과로 count를 반환합니다.
예시
#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<<"Count of number of substrings with exactly k distinct characters are: "<<substring_k(str, length, k);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count of number of substrings with exactly k distinct characters are: 3