Leetcode 1419: Minimum Number of Frogs Croaking

 https://leetcode.com/problems/minimum-number-of-frogs-croaking/description/

Notes:

This question can be solved in a greedy way.

We need to record some key information during scanning. 

For example, 

1): once we meet with a 'c', we should see whether there are available frog or not. If yes, no new frog is needed; otherwise, need a new frog;

2): once we meet with a 'r', we need to make sure there is at least one frog is yelling 'c'. If no, return -1;

if yes, need to update the counting on 'r' and 'c', respectively;

3): if 'o' or 'a', then it is similar to 2);

4): if 'k', similar to 2). but once difference is that: we only need to update the counting on 'a'. Then one more frog becomes available for the next round of yelling;

5): after scanning the string, we need to make sure all the frogs finish their yelling. This is can be done by scanning the counting of each letter. If all zero, it means all done; o/w, return -1.

6): return number of frog needed.

See the code below:

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        int n = croakOfFrogs.size(), res = 0, rm = 0;
        unordered_map<char, int> mp;
        for(auto &c : croakOfFrogs) {
            if(c=='c') {
                if(rm>0) --rm;
                else ++res;
                ++mp['c'];
            } else if(c == 'r') {
                if(!check(mp, 'c', 'r')) return -1;
            } else if(c == 'o') {
                if(!check(mp, 'r', 'o')) return -1;
            } else if(c == 'a') {
                if(!check(mp, 'o', 'a')) return -1;
            } else if(c == 'k') {
                if(!mp.count('a') || mp['a'] == 0) return -1;
                --mp['a'];
                ++rm;
            } else {
                return -1;
            }
        }
        for(auto &a : mp) {
            if(a.second > 0) return -1;
        }
        return res;
    }
private:
    bool check(unordered_map<char, int>& mp, char a, char b) {
        if(!mp.count(a) || mp[a] == 0) return false;
        --mp[a];
        ++mp[b];
        return true;
    }
};