Đếm số chuỗi có thể tạo từ chuỗi khác dùng mỗi ký tự tối đa một lần trong C++

Cho hai chuỗi str1 và str2. Nhiệm vụ: đếm số lần có thể tạo ra str2 hoàn toàn từ các ký tự của str1, mỗi ký tự trong str1 chỉ dùng tối đa một lần cho mỗi lần tạo.

Ví dụ

Đầu vào − str_1 = "technical learning", str_2 = "learning"

Đầu ra − 1

Giải thích − str_2 xuất hiện trong str_1 đúng 1 lần.

Đầu vào − str_1 = "ellohsehelloabcoelhl", str_2 = "hello"

Đầu ra − 3

Giải thích − Có 3 bộ ký tự 'h','e','l','l','o' trong str_1 để tạo "hello".

Phương pháp giải

Đếm tần suất mỗi ký tự trong str1 (mảng 26 phần tử). Với mỗi ký tự trong str2, số lần tạo được tối đa là min của tần suất trong str1. Kết quả là min của tất cả các ký tự trong str2.

• Hàm atmost_once(string str_1, int len1, string str_2, int len2).
• Khởi tạo count = INT_MAX, mảng arr[26] = {0}.
• Đếm tần suất str_1: arr[str_1[i]-'a']++.
• Duyệt str_2: count = min(count, arr[str_2[i]-'a']).
• Trả về count.

Ví dụ code

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

int atmost_once(string str_1, int len_str1, string str_2, int len_str2) {
    int count = INT_MAX;
    int arr[26] = {0};
    for (int i = 0; i < len_str1; i++) arr[str_1[i] - 'a']++;
    for (int i = 0; i < len_str2; i++) count = min(count, arr[str_2[i] - 'a']);
    return count;
}

int main() {
    string str_1 = "technical learning";
    int length_str1 = str_1.length();
    string str_2 = "learning";
    int length_str2 = str_2.length();
    cout << "Count of strings that can be formed from another string using each character at-most once are: " << atmost_once(str_1, length_str1, str_2, length_str2);
    return 0;
}

Đầu ra

Count of strings that can be formed from another string using each character at-most once are: 1