두 개의 문자열 str_1 및 str_2가 입력으로 제공됩니다. 각 문자가 한 번만 사용되는 str_1에서 선택한 문자를 사용하여 구성할 수 있는 str_2와 동일한 문자열의 개수를 찾는 것이 목표입니다.
참고 − 두 알파벳 모두 대소문자가 같습니다.
예를 들어 이해합시다.
입력 - str_1 ="abcaaaabca", str_2 ="bca";
출력 − 주어진 다른 문자열에서 구성할 수 있는 문자열의 발생 횟수는 다음과 같습니다. 2
설명 − str_a의 하위 문자열 bca −
str_1[1-3]=”bca” and str[7-9]=”bca”
입력 - str_1 ="약", str_2 ="cout";
출력 − 주어진 다른 문자열에서 구성할 수 있는 문자열의 발생 횟수는 − 0
입니다.설명 − 부분 문자열 cout이 str_a에 없습니다.
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
먼저 str_1에 있는 모든 알파벳의 빈도를 계산하여 arr_1[26] 배열에 저장하고 arr_2에 있는 모든 알파벳의 빈도를 arr_2[26] 배열에 저장합니다.
-
두 개의 문자열 str_1과 str_2를 가져옵니다. 길이를 str_1.size() 및 str_2.size()로 계산합니다.
-
count_string(string str_1, int len_str_1, string str_2, int len_str_2) 함수는 문자열과 길이를 모두 사용하여 str_1에서 구성할 수 있는 문자열 str_2의 수를 반환합니다.
-
초기 카운트를 INT_MAX로 간주합니다.
-
str_1의 문자 빈도에 대해 두 개의 배열 arr_1[26]을 초기화하고 arr_2의 문자 빈도에 대해 0으로 초기화합니다.
-
for 루프를 사용하여 str_1과 str_2를 모두 트래버스하고 arr_1 및 arr_2에서 빈도를 업데이트합니다.
-
이제 for 루프를 사용하여 arr_2를 다시 탐색하고 현재 주파수 arr_2[i]가 0이 아닌 경우 count(이전 값) 및 arr_1[i]/arr_2[i]의 최소값( str_1의 각 알파벳은 str_2의 각 문자에 대해 한 번만 가져옴) .
-
결국, count는 str_1과 str_2의 일치하는 대응하는 문자의 최소값을 가질 것입니다. 예 aaabbbb(a=3,b=4) 및 abb(a=1,b=2) 최소 개수는 1입니다.
-
모든 루프의 끝에서 원하는 결과로 카운트를 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int count_string(string str_1, int length_str_1, string str_2, int length_str_2){
int count = INT_MAX;
int arr_1[26] = { 0 };
int arr_2[26] = { 0 };
for (int i = 0; i < length_str_1; i++){
arr_1[str_1[i] - 'a']++;
}
for (int i = 0; i < length_str_2; i++){
arr_2[str_2[i] - 'a']++;
}
int total_alphabets = 26;
for (int i = 0; i < total_alphabets; i++){
if(arr_2[i]){
count = min(count, arr_1[i] / arr_2[i]);
}
}
return count;
}
int main(){
string str_1 = "knowledge", str_2 = "know";
int length_str_1 = str_1.size();
int length_str_2 = str_2.size();
cout<<"Count occurrences of a string that can be constructed from another given string are: "<<count_string(str_1,length_str_1, str_2, length_str_2);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count occurrences of a string that can be constructed from another given string are: 1