Minimum Number of Frogs Croaking
MedPrompt
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 <= 105croakOfFrogsis either'c','r','o','a', or'k'.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
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 = 0to track the peak number of frogs used. - Iterate through each character
chof the input stringcroakOfFrogs:- If
chis 'c':- Linearly scan the
frogslist 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()).
- Linearly scan the
- If
chis 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
frogslist 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).
- If
- After the loop, iterate through the
frogslist 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.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize separate queues for each state of the croak:
c_q,r_q,o_q,a_q. - Initialize
frogs_in_use = 0andmax_frogs = 0. - Iterate through each character
chofcroakOfFrogs:- If
ch == 'c': A frog starts croaking. Enqueue a placeholder toc_q, incrementfrogs_in_use, and updatemax_frogs = max(max_frogs, frogs_in_use). - If
ch == 'r': A frog must transition from state 'c' to 'r'. Check ifc_qis empty. If so, return -1. Otherwise, dequeue fromc_qand enqueue tor_q. - If
ch == 'o': Check ifr_qis empty. If so, return -1. Otherwise, dequeue fromr_qand enqueue too_q. - If
ch == 'a': Check ifo_qis empty. If so, return -1. Otherwise, dequeue fromo_qand enqueue toa_q. - If
ch == 'k': A frog finishes its croak. Check ifa_qis empty. If so, return -1. Otherwise, dequeue froma_qand decrementfrogs_in_use.
- If
- After the loop, if
frogs_in_useis not 0, it means some croaks were not completed. Return -1. - Otherwise, return
max_frogs.
Walkthrough
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.
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; } }}Complexity
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.
Trade-offs
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.
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.
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 = 0andmax_frogs = 0. - Iterate through each character
chofcroakOfFrogs:- If
ch == 'c': A new croak begins. Incrementc, incrementfrogs_in_use, and updatemax_frogs = max(max_frogs, frogs_in_use). - If
ch == 'r': A frog must be available from the 'c' state. Ifc == 0, return -1. Otherwise, decrementcand incrementr. - If
ch == 'o': A frog must be available from the 'r' state. Ifr == 0, return -1. Otherwise, decrementrand incremento. - If
ch == 'a': A frog must be available from the 'o' state. Ifo == 0, return -1. Otherwise, decrementoand incrementa. - If
ch == 'k': A frog must be available from the 'a' state. Ifa == 0, return -1. Otherwise, decrementaand decrementfrogs_in_useas one frog is now free.
- If
- After the loop, if
frogs_in_useis not 0 (or equivalently, ifc,r,o, oraare non-zero), it means some frogs did not complete their croak. Return -1. - Otherwise, the string is valid, and the answer is
max_frogs.
Walkthrough
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).
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; } }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.