<p>You are given the string <code>croakOfFrogs</code>, which represents a combination of the string <code>&quot;croak&quot;</code> from different frogs, that is, multiple frogs can croak at the same time, so multiple <code>&quot;croak&quot;</code> are mixed.</p>

<p><em>Return the minimum number of </em>different<em> frogs to finish all the croaks in the given string.</em></p>

<p>A valid <code>&quot;croak&quot;</code> means a frog is printing five letters <code>&#39;c&#39;</code>, <code>&#39;r&#39;</code>, <code>&#39;o&#39;</code>, <code>&#39;a&#39;</code>, and <code>&#39;k&#39;</code> <strong>sequentially</strong>. The frogs have to print all five letters to finish a croak. If the given string is not a combination of a valid <code>&quot;croak&quot;</code> return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> croakOfFrogs = &quot;croakcroak&quot;
<strong>Output:</strong> 1 
<strong>Explanation:</strong> One frog yelling &quot;croak<strong>&quot;</strong> twice.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> croakOfFrogs = &quot;crcoakroak&quot;
<strong>Output:</strong> 2 
<strong>Explanation:</strong> The minimum number of frogs is two. 
The first frog could yell &quot;<strong>cr</strong>c<strong>oak</strong>roak&quot;.
The second frog could yell later &quot;cr<strong>c</strong>oak<strong>roak</strong>&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> croakOfFrogs = &quot;croakcrook&quot;
<strong>Output:</strong> -1
<strong>Explanation:</strong> The given string is an invalid combination of &quot;croak<strong>&quot;</strong> from different frogs.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= croakOfFrogs.length &lt;= 10<sup>5</sup></code></li>
	<li><code>croakOfFrogs</code> is either <code>&#39;c&#39;</code>, <code>&#39;r&#39;</code>, <code>&#39;o&#39;</code>, <code>&#39;a&#39;</code>, or <code>&#39;k&#39;</code>.</li>
</ul>

class Solution {
    unordered_map<char, int> frequency; // Stores how many times each sound has occured. Sounds are c, r, o, a, k. 
    /* At any time, for a sequence to be valid, number of 'c' must not be less than 'r'.
     * Similarly, #'r' shouldn't  less than #'o', and so on. */
    bool isStateValid() {
         return (frequency['c'] >= frequency['r']) &&
                (frequency['r'] >= frequency['o']) &&
                (frequency['o'] >= frequency['a']) && 
                (frequency['a'] >= frequency['k']);
    }
    
public:
    /*
     *  Minimum number of frogs that we need is maximum number of frogs that are croaking
     *  simultaneously.
     *  Each "croaking" is a sequence of c, r, o, a, and k.
     *  Sound is a character in croakSequence.
     */
    int minNumberOfFrogs(string croakSequence) {
        int numCroakingFrogs = 0; // Number of distinct frogs that are croaking at any given time.
        int answer = 0; // Hold the final answer.
        for (char &sound: croakSequence) { // for each sound i.e. character.
            frequency[sound]++; // Note the sound.
            if (!isStateValid()) { // Make sure we are still in valid state.
                return -1;
            }
            if (sound == 'c') { // New "croaking" always begins at 'c'.
                numCroakingFrogs++; // Addional frog for the new "croaking".
            } else if (sound == 'k') { // A "croaking" ends at 'k'.
                numCroakingFrogs--; // Some frog has stopped croaking now.
            }
            answer = max(answer, numCroakingFrogs); // Maximum number of frogs that are croaking 
                                                    // simultaneously over a period.
        }
        return numCroakingFrogs == 0 ? answer : -1; // Make sure all frogs have completed the croaking.
    }
};


// class Solution {
// public:
//     int minNumberOfFrogs(string croakOfFrogs) 
//     {
//         int cnt[5] = {}, frogs = 0, max_frogs = 0;
        
//         for (auto ch : croakOfFrogs) {
//             auto n = string("croak").find(ch);
//             ++cnt[n];
//             if (n == 0) 
//                 max_frogs = max(max_frogs, ++frogs);
//             else if (--cnt[n - 1] < 0)
//                 return -1;
//             else if (n == 4)
//                 --frogs;
//         }
        
//         return frogs == 0 ? max_frogs : -1;
        
//     }
// };


// // We can track how many frogs are 'singing' each letter in cnt:
// // Increase number of frogs singing this letter, and decrease number singing previous letter.
// // When a frog sings 'c', we increase the number of (simultaneous) frogs.
// // When a frog sings 'k', we decrease the number of (simultaneous) frogs.
// // If some frog is singing a letter, but no frog sang the previous letter, we return -1.
// // Track and return the maximum number of frogs ever signing together.
// // Catch: if some frog hasn't finished cr


13100