How to find the minimum number of frogs croaking in LeetCode problem 1419?

本文共计547个文字，预计阅读时间需要3分钟。

描述：给定字符串croakOfFrogs，它代表不同青蛙发出的croak声的组合。也就是说，多只青蛙可以同时发出croak声，因此多个croak声会混合在一起。返回至少需要多少只青蛙才能发出这个声音序列。

Description

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’.

分析

题目的意思是：给定一个字符串，问最少由多少个croak字符串组成，其中croak可以分开，这种情况要单独算一种。这道题要找规律，首先统计字符的频率，如果出现了其他字符，则直接返回-1.最后统计出来的频率要相等，否则也要返回-1.如何统计croak的数量呢，用一个cur来统计当前c字符的数量，如果遇见k要减1，维护最小值res就行了，这个要找规律，不然就麻烦，哈哈。

代码

class Solution:
def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
d=collections.defaultdict(int)
cur=0
res=0
for ch in croakOfFrogs:
d[ch]+=1
if(ch=='c'):
cur+=1
elif(ch=='k'):
cur-=1
res=max(res,cur)
if(d['c']<d['r'] or d['r']<d['o'] or d['o']<d['a'] or d['a']<d['k']):
return -1
if(d['c']==d['r'] and d['r']==d['o'] and d['o']==d['a'] and d['a']==d['k']):
return res
return -1

参考文献

​​[LeetCode] Py O(n) Sol: Easy to Understand, Ask Doubt​​