<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:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        # A function to find the next letter to form croak
        def get_next_letter(current_letter):
            next_letters = {
                'c': 'r',
                'r': 'o',
                'o': 'a',
                'a': 'k',
                'k': None
            }

            return next_letters.get(current_letter, None)
        
        # Maintain a count of all the letters expected next
        letter_expectations = {
            'r': 0,
            'o': 0,
            'a': 0,
            'k': 0,
        }

        # A counter to maintain the number of ongoing croaks
        num_ongoing_croaks = 0
        # A counter to maintain the number of completed croaks
        num_completed_croaks = 0
        # A list to keep track of the next expected letter to form a croak
        next_expected_letters = list()

        for i, letter in enumerate(croakOfFrogs):
            # Check if it is a valid letter in croak
            if letter not in {'c', 'r', 'o', 'a', 'k'}:
                return -1
            
            # Check if it can be the next letter in an ongoing croak
            if letter in letter_expectations and letter_expectations[letter] > 0:
                # Pop that letter from list
                letter_expectations[letter] -= 1
                # Get the next expected letter for this
                next_letter = get_next_letter(letter)
                if next_letter is None:
                    # Mark it as completed
                    num_completed_croaks += 1
                    # Reduce ongoing croaks
                    num_ongoing_croaks -= 1
                    # Move on
                    continue
                # If it is a valid letter, add it
                letter_expectations[next_letter] += 1
                # Move to the next letter
                continue
            
            # If the letter is in croak and is not in expected_letters, check if it is 'c' - begnning of a croak
            if not letter == 'c':
                # If not, its not possible to form a valid croak
                return -1
            # If it is c, add it to num ongoing croaks
            # First check if ongoing crocks are 0, if yes, set completed to 0 as well
            if num_completed_croaks > 0:
                num_completed_croaks -= 1
            # Increment num_ongoing_croaks
            num_ongoing_croaks += 1
            # Add to next expected letters
            letter_expectations[get_next_letter(letter)] += 1

        if num_ongoing_croaks > 0:
            return -1
        
        return num_completed_croaks
212