今天討論 Counter 邊走邊消除的技巧。

1419. Minimum Number of Frogs Croaking (Medium)

題目敘述:

給你字串croakOfFrogs，它代表來自不同青蛙的字串「croak」的組合，也就是說，多個青蛙可以同時鳴叫，因此多個「croak」是混合的。 傳回完成給定字串中所有呱呱叫聲的不同青蛙的最小數量。
有效的「呱呱」表示青蛙正在依序列印五個字母「c」、「r」、「o」、「a」和「k」。青蛙必須印出五個字母才能完成呱呱叫。如果給定的字串不是有效的“croak”的組合，則傳回 -1。

解題:
這些「croak」是交錯發生的，所以無法簡單地將字串按順序分成多個「croak」序列，而是需要動態地追蹤每一隻青蛙的發聲進度。

這題兩個重點:

1. 確保每個青蛙的鳴叫「croak」序列是按順序完成的。
2. 最小化需要的青蛙數量，也就是處理多隻青蛙在不同階段發出不同字母的情況。

要確定「croak」 的順序，是邊走邊消的技巧。

每次遇到一個字母時，要確認它的前一個字母是否有相對應的出現。也就是說，當你遇到'r'時，必須要有一個先前出現的'c'，並且要消耗掉一個'c'，這代表一隻青蛙從「c」階段進入了「r」階段。

每個字元（比如 'r'）必須依賴於前一個字元（比如 'c'）的完成，否則字串順序就無法成立。而我的作法，迭代某字元就計數 +1，藉此得知某字元是否完成了。那「完成」可以具象想像成一個禮物，像是有一個人拿著一個禮物，拿給隊伍第一個人，然後他們需要轉傳到最後一人。如果上一個人沒有「禮物」，那麼整個過程就會中斷。
(不知道這樣描述會不會更抽象了?)

要確定字元前後關係，我是用 hash map，去對應字元與其位置。
'c' -> 0, 'r' -> 1, 'o' -> 2, 'a' -> 3, 'k' -> 4

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        int activeFrog = 0, maxFrogs = 0;

        // mp['c'] = 0, mp['r'] = 1 ...
        unordered_map <char, int> mp;
        string str = "croak"; 
        for (int i = 0; i < str.size(); i++) {
            mp[str[i]] = i;
        }
        vector<int> cnt (5, 0);
        for (char c: croakOfFrogs) {
            int pos = mp[c];
            cnt[pos] += 1; 
            if (pos == 0) {
                maxFrogs = max(maxFrogs, ++activeFrog);
            } 
            else if (--cnt[pos-1] < 0) return -1;
            else if (pos == 4) 
                activeFrog--;
        }
        return activeFrog == 0? maxFrogs: -1;
    }
};