# Minimum Number of Frogs Croaking
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-frogs-croaking)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-frogs-croaking
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** String
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [Zoox](https://scaleengineer.com/companies/zoox)
---
## Problem
You are given the string `croakOfFrogs`, which represents a combination of the string `"croak"` from different frogs, that is, multiple frogs can croak at the same time, so multiple `"croak"` are mixed.

_Return the minimum number of_ different _frogs to finish all the croaks in the given string._

A valid `"croak"` means a frog is printing five letters `'c'`, `'r'`, `'o'`, `'a'`, and `'k'` **sequentially**. The frogs have to print all five letters to finish a croak. If the given string is not a combination of a valid `"croak"` return `-1`.

**Example 1:**

**Input:** croakOfFrogs = "croakcroak"
**Output:** 1 
**Explanation:** One frog yelling "croak**"** twice.

**Example 2:**

**Input:** croakOfFrogs = "crcoakroak"
**Output:** 2 
**Explanation:** The minimum number of frogs is two. 
The first frog could yell "**cr**c**oak**roak".
The second frog could yell later "cr**c**oak**roak**".

**Example 3:**

**Input:** croakOfFrogs = "croakcrook"
**Output:** -1
**Explanation:** The given string is an invalid combination of "croak**"** from different frogs.

**Constraints:**

* `1 <= croakOfFrogs.length <= 105`
* `croakOfFrogs` is either `'c'`, `'r'`, `'o'`, `'a'`, or `'k'`.

# Approaches
## Brute-force Simulation
This approach directly simulates the process by maintaining a list of all frogs and their current states (e.g., idle, said 'c', said 'cr', etc.). For each character in the input string, it performs a linear search through the list to find a frog in the appropriate preceding state to advance it. If a 'c' is encountered, it first tries to reuse an idle frog; if none are available, a new frog is created. The minimum number of frogs is the maximum size the list of frogs ever reaches.
**Time:** O(N * F), where N is the length of the string and F is the maximum number of frogs. For each of the N characters, we might scan the entire list of F frogs. Since F can be proportional to N, this leads to a worst-case complexity of O(N^2). · **Space:** O(F) or O(N), where F is the maximum number of concurrent frogs. In the worst-case scenario like 'ccccc...', the number of frogs can be up to N/5.
**Pros:** Conceptually simple and directly models the problem statement.; Easy to understand and implement.
**Cons:** Highly inefficient, with a time complexity of O(N^2) in the worst case, which will likely time out on larger inputs.; The space complexity is proportional to the number of frogs, which can be large.
### Explanation
This method provides a straightforward simulation of the frog croaking process. We use a `List` where each element represents a frog and its value represents the frog's current state in the 'c'-'r'-'o'-'a'-'k' sequence. When a 'c' appears, we need a frog. We first check if any existing frog is idle and can be reused. If not, we must introduce a new frog, increasing our count of total frogs. For any other letter, we must find a frog that is waiting to say that letter. This involves searching our entire list of frogs. The main drawback is this repeated search, which makes the solution slow for long input strings.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        // States: -1 (idle), 0 ('c'), 1 ('r'), 2 ('o'), 3 ('a')
        List<Integer> frogs = new ArrayList<>();
        int maxFrogs = 0;
        
        String croak = "croak";

        for (char ch : croakOfFrogs.toCharArray()) {
            int targetState = croak.indexOf(ch);
            int prevState = targetState - 1;
            boolean foundFrog = false;

            if (ch == 'c') {
                // Try to find an idle frog
                for (int i = 0; i < frogs.size(); i++) {
                    if (frogs.get(i) == -1) {
                        frogs.set(i, 0);
                        foundFrog = true;
                        break;
                    }
                }
                // If no idle frog, create a new one
                if (!foundFrog) {
                    frogs.add(0);
                    maxFrogs = Math.max(maxFrogs, frogs.size());
                }
            } else {
                // Find a frog in the previous state
                for (int i = 0; i < frogs.size(); i++) {
                    if (frogs.get(i) == prevState) {
                        // If it's the last letter, frog becomes idle
                        int nextState = (targetState == 4) ? -1 : targetState;
                        frogs.set(i, nextState);
                        foundFrog = true;
                        break;
                    }
                }
                // If no frog was ready for this letter, invalid sequence
                if (!foundFrog) {
                    return -1;
                }
            }
        }

        // Check for any unfinished croaks
        for (int state : frogs) {
            if (state != -1) {
                return -1;
            }
        }

        return maxFrogs;
    }
}
```
### Algorithm
- Initialize an empty list, `frogs`, to store the state of each frog. A state can be represented by an integer: -1 for idle, 0 for 'c', 1 for 'r', 2 for 'o', 3 for 'a'.
- Initialize `max_frogs = 0` to track the peak number of frogs used.
- Iterate through each character `ch` of the input string `croakOfFrogs`:
  - If `ch` is 'c':
    - Linearly scan the `frogs` list for an idle frog (state -1). 
    - If an idle frog is found, change its state to 0 ('c').
    - If no idle frog is found, a new frog is required. Add a new frog with state 0 to the list and update `max_frogs = max(max_frogs, frogs.size())`.
  - If `ch` is not 'c' (e.g., 'r', 'o', 'a', 'k'):
    - Determine the required previous state (e.g., for 'r', the previous state is 'c').
    - Linearly scan the `frogs` list to find a frog in that previous state.
    - If no such frog exists, the string is invalid. Return -1.
    - If a frog is found, update its state to the current character's state. If the character is 'k', the frog finishes its croak and its state becomes idle (-1).
- After the loop, iterate through the `frogs` list one last time. If any frog is not in the idle state, it means there's an incomplete croak. Return -1.
- Otherwise, the string is valid. Return `max_frogs`.

## Optimized Simulation with Queues
This approach improves upon the brute-force simulation by using dedicated data structures, specifically queues, to manage frogs in different states of their croak. Instead of linearly searching for a frog in the correct state, we can simply dequeue a frog from the appropriate queue in O(1) time. This significantly speeds up the process, reducing the time complexity from quadratic to linear.
**Time:** O(N), where N is the length of the string. Each character is processed once with O(1) queue operations. · **Space:** O(F) or O(N), where F is the maximum number of concurrent frogs. In the worst case (e.g., 'ccccc...'), the 'c' queue can grow to a size of N/5.
**Pros:** Efficient O(N) time complexity.; Still conceptually follows the simulation idea but in an optimized way.
**Cons:** Requires extra space for the queues, which can be up to O(N) in the worst case.
### Explanation
By categorizing frogs based on the sound they last made, we can optimize the search. We maintain a queue for each sound ('c', 'r', 'o', 'a'). When we see a 'c', we start a new croak, incrementing the count of active frogs. When we see an 'r', we take a frog from the 'c' queue and move it to the 'r' queue. This continues for all letters. A 'k' signifies a finished croak, so a frog becomes free, and the active frog count decreases. This avoids the O(N) scan of the previous approach, making each step an O(1) operation.

```java
import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        // Using queues to represent frogs in each state
        Queue<Integer> c = new ArrayDeque<>();
        Queue<Integer> r = new ArrayDeque<>();
        Queue<Integer> o = new ArrayDeque<>();
        Queue<Integer> a = new ArrayDeque<>();
        
        int frogsInUse = 0;
        int maxFrogs = 0;

        for (char ch : croakOfFrogs.toCharArray()) {
            switch (ch) {
                case 'c':
                    c.offer(1); // Add a frog to the 'c' state
                    frogsInUse++;
                    maxFrogs = Math.max(maxFrogs, frogsInUse);
                    break;
                case 'r':
                    if (c.isEmpty()) return -1;
                    c.poll();
                    r.offer(1);
                    break;
                case 'o':
                    if (r.isEmpty()) return -1;
                    r.poll();
                    o.offer(1);
                    break;
                case 'a':
                    if (o.isEmpty()) return -1;
                    o.poll();
                    a.offer(1);
                    break;
                case 'k':
                    if (a.isEmpty()) return -1;
                    a.poll();
                    frogsInUse--; // A frog is now free
                    break;
            }
        }

        // If frogsInUse is 0, all started croaks were finished.
        // Also implies all intermediate queues (c,r,o,a) are empty.
        if (frogsInUse == 0) {
            return maxFrogs;
        } else {
            return -1;
        }
    }
}
```
### Algorithm
- Initialize separate queues for each state of the croak: `c_q`, `r_q`, `o_q`, `a_q`.
- Initialize `frogs_in_use = 0` and `max_frogs = 0`.
- Iterate through each character `ch` of `croakOfFrogs`:
  - If `ch == 'c'`: A frog starts croaking. Enqueue a placeholder to `c_q`, increment `frogs_in_use`, and update `max_frogs = max(max_frogs, frogs_in_use)`.
  - If `ch == 'r'`: A frog must transition from state 'c' to 'r'. Check if `c_q` is empty. If so, return -1. Otherwise, dequeue from `c_q` and enqueue to `r_q`.
  - If `ch == 'o'`: Check if `r_q` is empty. If so, return -1. Otherwise, dequeue from `r_q` and enqueue to `o_q`.
  - If `ch == 'a'`: Check if `o_q` is empty. If so, return -1. Otherwise, dequeue from `o_q` and enqueue to `a_q`.
  - If `ch == 'k'`: A frog finishes its croak. Check if `a_q` is empty. If so, return -1. Otherwise, dequeue from `a_q` and decrement `frogs_in_use`.
- After the loop, if `frogs_in_use` is not 0, it means some croaks were not completed. Return -1.
- Otherwise, return `max_frogs`.

## Single Pass with State Counting
This is the most optimal approach, achieving linear time and constant space complexity. Instead of tracking individual frogs or using data structures that scale with input, we only need to maintain a few counters. We count how many frogs are currently in each phase of the croak (i.e., have said 'c' and are waiting for 'r', have said 'r' and are waiting for 'o', etc.). By iterating through the string once and updating these counts, we can validate the sequence and determine the peak number of frogs active at any single moment.
**Time:** O(N), as it requires only a single pass through the input string. · **Space:** O(1), as we only use a fixed number of integer variables to store counts, regardless of the input string's size.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Simple and elegant implementation once the logic is understood.
**Cons:** The logic can be slightly less intuitive to derive compared to direct simulation.
### Explanation
The core insight is that we don't need to know *which* frog is croaking, only *how many* frogs are in each state. We can use simple integer counters for this. `c` will count frogs that have said 'c' and are waiting, `r` for those that said 'r', and so on. When a 'c' is read, a new frog becomes active, so we increment the `c` counter and the total `frogs_in_use`. When an 'r' is read, a frog transitions from the 'c' state to the 'r' state, so we decrement `c` and increment `r`. This continues for the whole sequence. A 'k' frees up a frog, so `frogs_in_use` decreases. The maximum value that `frogs_in_use` reaches during this process is the minimum number of frogs required. We must also perform checks at each step to ensure no sound is made out of order (e.g., an 'r' cannot be made if no frog is in the 'c' state).

```java
class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        // counts of frogs that are in the middle of a croak
        int c = 0, r = 0, o = 0, a = 0; 
        int frogsInUse = 0;
        int maxFrogs = 0;

        if (croakOfFrogs.length() % 5 != 0) {
            return -1;
        }

        for (char ch : croakOfFrogs.toCharArray()) {
            switch (ch) {
                case 'c':
                    c++;
                    frogsInUse++;
                    maxFrogs = Math.max(maxFrogs, frogsInUse);
                    break;
                case 'r':
                    if (c == 0) return -1;
                    c--;
                    r++;
                    break;
                case 'o':
                    if (r == 0) return -1;
                    r--;
                    o++;
                    break;
                case 'a':
                    if (o == 0) return -1;
                    o--;
                    a++;
                    break;
                case 'k':
                    if (a == 0) return -1;
                    a--;
                    frogsInUse--;
                    break;
                default:
                    return -1;
            }
        }

        // If frogsInUse is 0, all started croaks were finished.
        // This also implies c, r, o, a are all 0.
        if (frogsInUse == 0) {
            return maxFrogs;
        } else {
            return -1;
        }
    }
}
```
### Algorithm
- Initialize four counters to zero: `c`, `r`, `o`, `a`. These will track the number of frogs that have said the respective letter but have not yet proceeded to the next one.
- Initialize `frogs_in_use = 0` and `max_frogs = 0`.
- Iterate through each character `ch` of `croakOfFrogs`:
  - If `ch == 'c'`: A new croak begins. Increment `c`, increment `frogs_in_use`, and update `max_frogs = max(max_frogs, frogs_in_use)`.
  - If `ch == 'r'`: A frog must be available from the 'c' state. If `c == 0`, return -1. Otherwise, decrement `c` and increment `r`.
  - If `ch == 'o'`: A frog must be available from the 'r' state. If `r == 0`, return -1. Otherwise, decrement `r` and increment `o`.
  - If `ch == 'a'`: A frog must be available from the 'o' state. If `o == 0`, return -1. Otherwise, decrement `o` and increment `a`.
  - If `ch == 'k'`: A frog must be available from the 'a' state. If `a == 0`, return -1. Otherwise, decrement `a` and decrement `frogs_in_use` as one frog is now free.
- After the loop, if `frogs_in_use` is not 0 (or equivalently, if `c`, `r`, `o`, or `a` are non-zero), it means some frogs did not complete their croak. Return -1.
- Otherwise, the string is valid, and the answer is `max_frogs`.

# Solutions
### Java

```java
class Solution {
public
  int minNumberOfFrogs(String croakOfFrogs) {
    int n = croakOfFrogs.length();
    if (n % 5 != 0) {
      return -1;
    }
    int[] idx = new int[26];
    String s = "croak";
    for (int i = 0; i < 5; ++i) {
      idx[s.charAt(i) - 'a'] = i;
    }
    int[] cnt = new int[5];
    int ans = 0, x = 0;
    for (int k = 0; k < n; ++k) {
      int i = idx[croakOfFrogs.charAt(k) - 'a'];
      ++cnt[i];
      if (i == 0) {
        ans = Math.max(ans, ++x);
      } else {
        if (--cnt[i - 1] < 0) {
          return -1;
        }
        if (i == 4) {
          --x;
        }
      }
    }
    return x > 0 ? -1 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minNumberOfFrogs(string croakOfFrogs) {
    int n = croakOfFrogs.size();
    if (n % 5 != 0) {
      return -1;
    }
    int idx[26]{};
    string s = "croak";
    for (int i = 0; i < 5; ++i) {
      idx[s[i] - 'a'] = i;
    }
    int cnt[5]{};
    int ans = 0, x = 0;
    for (char &c : croakOfFrogs) {
      int i = idx[c - 'a'];
      ++cnt[i];
      if (i == 0) {
        ans = max(ans, ++x);
      } else {
        if (--cnt[i - 1] < 0) {
          return -1;
        }
        if (i == 4) {
          --x;
        }
      }
    }
    return x > 0 ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    # class Solution : def minNumberOfFrogs ( self , croakOfFrogs : str ) -> int : c = r = o = a = k = ans = 0 for ch in croakOfFrogs : if ch == 'c' : c += 1 if k > 0 : k -= 1 else : ans += 1 elif ch == 'r' : r += 1 c -= 1 elif ch == 'o' : o += 1 r -= 1 elif ch == 'a' : a += 1 o -= 1 else : k += 1 a -= 1 if c < 0 or r < 0 or o < 0 or a < 0 : return - 1 return - 1 if c != 0 or r != 0 or o != 0 or a != 0 else ans ############ class Solution : def minNumberOfFrogs ( self , croakOfFrogs : str ) -> int : count = collections . Counter () prev = { "k" : "a" , "a" : "o" , "o" : "r" , "r" : "c" } res = 0 for c in croakOfFrogs : if c == "c" : count [ c ] += 1 else : if count [ prev [ c ]] > 0 : if c != "k" : count [ c ] += 1 count [ prev [ c ]] -= 1 else : return - 1 res = max ( res , sum ( count . values ())) return res if sum ( count . values ()) == 0 else - 1
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int: if not croakOfFrogs: return - 1 curr, res = 0, 0 c, r, o, a, k = 0, 0, 0, 0, 0 for each in croakOfFrogs: if each == 'c': c += 1 curr += 1 elif each == 'r': r += 1 elif each == 'o': o += 1 elif each == 'a': a += 1 else: k += 1 curr -= 1 res = max(res, curr) if c < r or r < o or o < a or a < k: return - 1 if c == r == o == a == k: return res return - 1

```