题目描述：
LeetCode 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'.
题目大意：
字符串croakOfFrogs表示来自不同青蛙的"croak"。由于多只青蛙可能会同时叫，所以"croak"可能会乱序。求可以得到croakOfFrogs的最小青蛙个数。如果字符串无效，则返回-1。
解题思路：
构建一个从"croak"中每个字符到它左边邻接字符的映射cmap：
k -> a, a -> o, o -> r, r -> c, c -> '#' （令"c"的左邻字符为哨兵字符"#"）
初始化字符计数器cnt，将哨兵字符"#"的计数初始化为极大值(len(croak) + 1)
遍历croakOfFrogs的每一个字符c，当cnt[cmap[c]] <= 0时，表示输入字符串是一个非法序列。
变量ans表示最终结果，frog表示出现当前字符c时的青蛙个数。
当c == 'c'时，令frog++，当c == 'k'时，令frog--
Python代码：
class Solution(object):
def minNumberOfFrogs(self, croakOfFrogs):
"""
:type croakOfFrogs: str
:rtype: int
"""
cmap = {'c': '#', 'r' : 'c', 'o': 'r', 'a' : 'o', 'k' : 'a'}
cnt = collections.defaultdict(int)
ans = frog = 0
cnt['#'] = len(croakOfFrogs) + 1
for c in croakOfFrogs:
if cnt[cmap[c]] <= 0: return -1
cnt[cmap[c]] -= 1
cnt[c] += 1
if c == 'c': frog += 1
elif c == 'k': frog -= 1
ans = max(frog, ans)
if sum(cnt.values()) > cnt['k'] + cnt['#']: return -1
return ans
本文链接：http://bookshadow.com/weblog/2020/05/01/leetcode-minimum-number-of-frogs-croaking/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
