จำนวนกบน้อยที่สุดที่ร้องได้ใน C++

สมมติว่าเรามีสตริง croakOfFrogs แทนเสียง "croak" ของกบหลายตัวผสมกัน หาจำนวนกบน้อยที่สุดที่ทำให้ได้สตริงนี้ หากไม่ valid คืน -1

ตัวอย่าง: "crcoakroak" → 2 กบ

วิธีแก้ปัญหา

1. นับความถี่ตัวอักษร c,r,o,a,k ใน map
2. ตลอดเวลา: count('c') ≥ count('r') ≥ count('o') ≥ count('a') ≥ count('k')
3. นับกบที่กำลังร้องพร้อมกัน (temp): +1 ตอน 'c', -1 ตอน 'k'
4. ค่าสูงสุดของ temp = คำตอบ
5. ท้ายสุด: count ทุกตัวต้องเท่ากัน

ตัวอย่างโค้ด C++

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

class Solution { 
public: 
    int minNumberOfFrogs(string s) { 
        map<char, int> m; 
        char ch[5] = {'c','r','o','a','k'}; 
        int temp = 0, ret = 0; 
        for (auto& c : s) { 
            m[c]++; 
            int maxVal = m[ch[0]]; 
            for (int i = 0; i < 5; i++) { 
                if (maxVal < m[ch[i]] || m[ch[i]] < 0) return -1; 
                maxVal = m[ch[i]]; 
            } 
            if (c == 'c') temp++; 
            else if (c == 'k') temp--; 
            ret = max(ret, temp); 
        } 
        for (int i = 1; i < 5; i++) 
            if (m[ch[0]] != m[ch[i]]) return -1; 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.minNumberOfFrogs("crcoakroak")); 
}

ข้อมูลนำเข้า

"crcoakroak"

ผลลัพธ์

2