# Question

Formatted question description: https://leetcode.ca/all/1419.html

 1419. Minimum Number of Frogs Croaking

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 croak in the given string.

A valid "croak" means a frog is printing 5 letters ‘c’, ’r’, ’o’, ’a’, ’k’ sequentially.
The frogs have to print all five letters to finish a croak.
If the given string is not a combination of 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.

Example 4:

Input: croakOfFrogs = "croakcroa"
Output: -1

Constraints:
1 <= croakOfFrogs.length <= 10^5
All characters in the string are: 'c', 'r', 'o', 'a' or 'k'.



# Algorithm

The idea is ​​scanning lines, but the step of judging the croak is greatly simplified. Every time we encounter the first ‘c’ and the last ‘k’. Directly subtract one from the previous character number of the current character.

If the previous digit is less than 0 after subtracting one, it means that there is no character before the current digit that matches it.

Assuming that our input is “crok”, when we traverse to k, the position of its previous ‘a’ is 0, indicating that we have one more string k. So there is no way to match.

The rest is the same as the scan line. When we encounter a new c, we add a frog and when we encounter k. We reduce a frog.

• [c, r, o, a, k], the number of characters at any time, in this order not ascending
• The final quantity must be equal
• The maximum of 5 characters at any time is the number of frogs needed
• If 5 characters are full of a frog, subtract it, and you can reuse the frog later.

# Code

Java

Java

class Solution {
public int minNumberOfFrogs(String croakOfFrogs) {
int length = croakOfFrogs.length();
if (length % 5 != 0)
return -1;
Map<Character, Integer> letterIndexMap = new HashMap<Character, Integer>();
String croak = "croak";
for (int i = 0; i < 5; i++)
letterIndexMap.put(croak.charAt(i), i);
int curSize = 0;
int maxSize = 0;
int[] counts = new int[5];
for (int i = 0; i < length; i++) {
char c = croakOfFrogs.charAt(i);
int index = letterIndexMap.get(c);
if (index == 0) {
counts[index]++;
curSize++;
maxSize = Math.max(maxSize, curSize);
} else {
counts[index - 1]--;
if (counts[index - 1] < 0)
return -1;
if (index < 4)
counts[index]++;
else
curSize--;
}
}
for (int i = 0; i < 5; i++) {
if (counts[i] != 0)
return -1;
}
return maxSize;
}
}