นับจำนวนสตริงที่สร้างได้จากอีกสตริงหนึ่งใน C++

เราได้รับสตริง 2 ตัว str_1 และ str_2 เป้าหมายคือหาว่าสามารถสร้าง str_2 ได้กี่ครั้งจากตัวอักษรใน str_1 (แต่ละตัวอักษรใน str_1 ใช้ได้เพียงครั้งเดียวต่อหนึ่ง str_2)

ตัวอย่าง

อินพุต: str_1 = "abcaaaabca", str_2 = "bca"

เอาต์พุต: 2

คำอธิบาย: str_1 มี a:5, b:2, c:2 str_2 ต้องการ a:1, b:1, c:1 สร้างได้ min(5/1, 2/1, 2/1) = 2 ครั้ง

อินพุต: str_1 = "about", str_2 = "cout"

เอาต์พุต: 0

คำอธิบาย: str_1 ไม่มีตัว 'c'

แนวทางการแก้ปัญหา

1. นับความถี่ตัวอักษรใน str_1 → arr_1[26]
2. นับความถี่ตัวอักษรใน str_2 → arr_2[26]
3. สำหรับแต่ละตัวอักษรที่มีใน str_2 คำนวณ arr_1[i] / arr_2[i]
4. คำตอบ = ค่า min ของทุกตัวอักษร

การนำไปใช้ (Implementation)

#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";
    int len1 = str_1.size(), len2 = str_2.size();
    cout << "Count occurrences of a string that can be constructed from another given string are: " << count_string(str_1, len1, str_2, len2);
    return 0;
}

เอาต์พุต

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