Đếm số lần chuỗi có thể tạo từ chuỗi khác trong C++

Cho 2 chuỗi str_1 và str_2. Đếm số chuỗi giống str_2 có thể tạo được từ các ký tự của str_1, mỗi ký tự trong str_1 chỉ dùng tối đa 1 lần cho mỗi bản sao.

Ví dụ

Đầu vào: str_1 = "abcaaaabca", str_2 = "bca"
Đầu ra: 2.

Đầu vào: str_1 = "about", str_2 = "cout"
Đầu ra: 0.

Giải thuật

Đếm tần suất ký tự trong str_1 (arr_1[26]) và str_2 (arr_2[26]). Kết quả = min over all chars của arr_1[c] / arr_2[c] (chỉ xét ký tự có trong str_2).

Ví dụ triển khai

#include <bits/stdc++.h>
using namespace std;

int count_string(string str_1, int len1, string str_2, int len2) {
    int arr_1[26] = {0}, arr_2[26] = {0};
    for (int i = 0; i < len1; i++) arr_1[str_1[i] - 'a']++;
    for (int i = 0; i < len2; i++) arr_2[str_2[i] - 'a']++;
    int count = INT_MAX;
    for (int i = 0; i < 26; i++) {
        if (arr_2[i] > 0) count = min(count, arr_1[i] / arr_2[i]);
    }
    return count;
}

int main() {
    string str_1 = "knowledge", str_2 = "know";
    cout << "Count occurrences of a string that can be constructed from another given string are: " << count_string(str_1, str_1.size(), str_2, str_2.size());
    return 0;
}

Kết quả

Count occurrences of a string that can be constructed from another given string are: 1