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 "crcoakroak". The second frog could yell later "crcoakroak".
Example 3:
Input: croakOfFrogs = "croakcrook" Output: -1 Explanation: The given string is an invalid combination of "croak" from different frogs.
Constraints:
1 <= croakOfFrogs.length <= 105croakOfFrogs is either 'c', 'r', 'o', 'a', or 'k'.Problem Overview: You receive a string representing overlapping frog sounds where each frog croaks the sequence "croak". Multiple frogs may croak simultaneously, so characters can interleave. The task is to verify the sequence is valid and compute the minimum number of frogs required to produce it.
Approach 1: Counter Technique by Stages (O(n) time, O(1) space)
Track how many frogs are currently at each stage of the word "croak". Maintain counters for characters c, r, o, a, and k. As you iterate through the string, move frogs from one stage to the next: when you see r, a frog must previously have produced c; when you see o, it must follow r, and so on. If a required previous stage does not exist, the sequence is invalid.
Each c either starts a new frog or reuses one that just finished with k. Track the number of active frogs (those mid‑croak) and update the maximum seen during traversal. That maximum represents the minimum frogs needed. Because only five counters are maintained and each character is processed once, the algorithm runs in O(n) time with O(1) space.
This approach works well because the croak sequence has a fixed order. Instead of tracking each frog individually, you track counts of frogs in each stage. Problems involving ordered character transitions often fall into string processing with lightweight counting techniques.
Approach 2: Hashmap Technique with Active Frogs (O(n) time, O(1) space)
Maintain a hashmap that records how many frogs are currently waiting for the next character in the croak sequence. For example, frogs that just produced c expect r, frogs at r expect o, and so on. Iterate through the string and update the map as frogs advance through the sequence.
If the current character cannot be matched with a frog waiting for that stage, the string is invalid. When a frog reaches k, its croak completes and that frog becomes available for reuse. Track how many frogs are active simultaneously to determine the minimum number required. The hashmap only stores counts for the five stages, so the memory usage stays constant.
This version models the lifecycle of each croak more explicitly. The logic is slightly easier to reason about when debugging because each step maps directly to the next expected character. It uses the same linear scan pattern commonly seen in hash map based tracking problems.
Recommended for interviews: The counter-by-stages solution is usually preferred. It demonstrates that you recognized the fixed "croak" progression and optimized the tracking to constant space. Explaining the invalid sequence checks and how active frogs determine the final answer shows strong control over string state transitions.
We utilize five counters to represent the stages of croaking: 'c', 'r', 'o', 'a', 'k'. As we iterate through the string, we manage these counters to ensure valid progression. Every time we encounter a 'c', we potentially introduce a new frog croaking. Similarly, we transition through each stage and ensure the order is maintained. Finally, the number of simultaneous croaks is the peak usage of the 'c' counter.
The function uses five counters to track frogs in each stage of 'croak'. The counters are updated as we traverse the string. If a 'c' is found, we start a new croak. For other characters, we check if there's a frog in the previous stage. The function returns -1 if an invalid sequence is detected, otherwise it returns the peak value of frogs croaking at the same time.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n), where n is the length of the input string, as we traverse the string once.
Space Complexity: O(1), as we use a fixed-size array of length 5.
This approach uses a hashmap to maintain the count of active 'croak' parts with a specific frog. We keep track of the characters seen and ensure that we have required preceding characters before we move to the next character. The map helps keep track of how many frogs are at each stage simultaneously to compute the minimum number of frogs required.
Here, a dictionary maintains counts of each letter in 'croak'. As we traverse, the active frog count grows with 'c' and shrinks with 'k', regulating sequence transitions. The checks ensure the validity of the sequence, returning -1 if violated.
Time Complexity: O(n), iterating through croakOfFrogs.
Space Complexity: O(1), storing fixed croak component counts.
We note that if the string croakOfFrogs is composed of several valid "croak" characters mixed together, its length must be a multiple of 5. Therefore, if the length of the string is not a multiple of 5, we can directly return -1.
Next, we map the letters 'c', 'r', 'o', 'a', 'k' to indices 0 to 4, respectively, and use an array cnt of length 5 to record the number of occurrences of each letter in the string croakOfFrogs, where cnt[i] represents the number of occurrences of the letter at index i. Additionally, we define an integer variable x to represent the number of frogs that have not completed their croak, and the minimum number of frogs needed ans is the maximum value of x.
We traverse each letter c in the string croakOfFrogs, find the index i corresponding to c, and then increment cnt[i] by 1. Next, depending on the value of i, we perform the following operations:
i=0, then a new frog starts croaking, so we increment x by 1, and then update ans = max(ans, x);cnt[i-1]=0, it means that there is no frog that can make the sound c, and the croak cannot be completed, so we return -1. Otherwise, we decrement cnt[i-1] by 1. If i=4, it means that a frog has completed a croak, so we decrement x by 1.After traversing, if x=0, it means that all frogs have completed their croaks, and we return ans. Otherwise, we return -1.
The time complexity is O(n), and the space complexity is O(C). Where n is the length of the string croakOfFrogs, and C is the size of the character set, in this problem C=26.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Counter Technique by Stages | Time Complexity: O(n), where n is the length of the input string, as we traverse the string once. |
| Hashmap Technique with Active Frogs | Time Complexity: O(n), iterating through croakOfFrogs. |
| Counting + Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counter Technique by Stages | O(n) | O(1) | Best overall solution when the sequence order is fixed and you only need stage counts |
| Hashmap with Active Frogs | O(n) | O(1) | Useful when modeling state transitions explicitly or extending the logic to longer sequences |
Minimum Number of Frogs Croaking| Leetcode 1419| Leetcode Weekly 185| Java| Hindi • Pepcoding • 3,016 views views
Watch 9 more video solutions →Practice Minimum Number of Frogs Croaking with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor