1419. Minimum Number of Frogs Croaking
Description
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'
.
Solutions
Solution 1: 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$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|