Skip to main content
Talentd

Minimum Number of Frogs Croaking - Solution & Explanation

MediumStringCounting20 min readAsked at: Roblox, Zoox
Practice this problem

Problem Statement

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 <= 105
  • croakOfFrogs is either 'c', 'r', 'o', 'a', or 'k'.

Approach Overview

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.

Approach 1: Counter Technique by Stages

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Hashmap Technique with Active Frogs

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.

Code

PythonC++Java

Python

C++

Java

Complexity

Time Complexity: O(n), iterating through croakOfFrogs.
Space Complexity: O(1), storing fixed croak component counts.

Try this approach in the editor →

Approach 3: Counting + Simulation

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:

  • If i=0, then a new frog starts croaking, so we increment x by 1, and then update ans = max(ans, x);
  • Otherwise, if 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Counter Technique by Stages

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.

Hashmap Technique with Active Frogs

Time Complexity: O(n), iterating through croakOfFrogs.
Space Complexity: O(1), storing fixed croak component counts.

Counting + Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Counter Technique by StagesO(n)O(1)Best overall solution when the sequence order is fixed and you only need stage counts
Hashmap with Active FrogsO(n)O(1)Useful when modeling state transitions explicitly or extending the logic to longer sequences

Video Solution

Minimum Number of Frogs Croaking| Leetcode 1419| Leetcode Weekly 185| Java| Hindi • Pepcoding • 3,034 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Number of Frogs Croaking easy or hard?
Minimum Number of Frogs Croaking is rated Medium difficulty. The challenge is recognizing that overlapping croaks represent frogs moving through fixed stages and ensuring invalid sequences are detected during the scan.
How to solve Minimum Number of Frogs Croaking in O(n)?
Scan the string once and track frogs at each stage of the word "croak". When you encounter a character, verify a frog exists in the previous stage and move it forward. Count how many frogs are active at the same time and record the maximum, which becomes the minimum number of frogs required.
Minimum Number of Frogs Croaking Python or Java solution?
Both Python and Java implementations follow the same idea: maintain counters for each stage of "croak" and update them while iterating through the string. The algorithm runs in O(n) time and uses constant extra memory.
What is the best approach for Minimum Number of Frogs Croaking?
The counter-by-stages approach is typically the best solution. It tracks how many frogs are at each stage of the sequence "croak" and moves them forward as characters appear. This method runs in O(n) time and O(1) space while also detecting invalid sequences early.
What data structure is used in Minimum Number of Frogs Croaking?
Most implementations use simple counters or a hashmap to track how many frogs are at each stage of the sequence. The counters represent transitions between characters in the ordered word "croak".
What is the time complexity of Minimum Number of Frogs Croaking?
The optimal solutions run in O(n) time where n is the length of the input string. Each character is processed exactly once while updating counters or a small hashmap. Space complexity stays O(1) because only five stage counts are stored.
Is Minimum Number of Frogs Croaking asked at Google, Amazon, or Meta?
Variants of this problem appear in interviews at companies like Amazon and Google because it tests string validation and state tracking. Interviewers expect candidates to recognize the fixed sequence pattern and solve it with a linear pass and constant memory.

Ready to solve this problem?

Practice Minimum Number of Frogs Croaking with our built-in code editor and test cases.

Practice on FleetCode
Previous

Divide Intervals Into Minimum Number of Groups