Số ếch kêu tối thiểu (Minimum Number of Frogs Croaking) trong C++

Cho chuỗi croakOfFrogs là trộn lẫn các từ "croak" của nhiều ếch (mỗi ếch kêu lần lượt c-r-o-a-k). Tìm số ếch tối thiểu. Nếu chuỗi không hợp lệ → -1.

Ví dụ

Đầu vào: "crcoakroak"
Đầu ra: 2.

Thuật toán đếm trạng thái

1. Duy trì đếm từng ký tự c,r,o,a,k trong map.
2. Duyệt chuỗi: tăng đếm ký tự hiện tại.
3. Kiểm tra tính hợp lệ: tại mọi thời điểm, đếm('c') ≥ đếm('r') ≥ ... ≥ đếm('k'). Nếu vi phạm → -1.
4. Khi gặp 'c': ếch mới bắt đầu kêu → active++.
5. Khi gặp 'k': ếch kết thúc → active--.
6. Theo dõi max(active) → số ếch cùng kêu lúc nào nhiều nhất = kết quả.
7. Cuối cùng: kiểm tra tất cả đếm bằng nhau (mỗi ếch kêu đủ 5 ký tự).

Triển khai C++

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

class Solution {
public:
    int minNumberOfFrogs(string s) {
        unordered_map cnt;
        string order = "croak";
        int active = 0, ans = 0;
        for (char c : s) {
            cnt[c]++;
            for (int i = 0; i < 5; ++i) {
                if (cnt[order[i]] < (i?cnt[order[i-1]]:0)) return -1;
            }
            if (c == 'c') ans = max(ans, ++active);
            else if (c == 'k') --active;
        }
        for (int i = 1; i < 5; ++i)
            if (cnt[order[i]] != cnt[order[0]]) return -1;
        return ans;
    }
};

Độ phức tạp

• Thời gian: O(N) - duyệt chuỗi một lần.
• Không gian: O(1) - map kích thước cố định 5.

Kết quả kiểm thử

Đầu vào: "crcoakroak"
Đầu ra: 2