What is the main challenge in Minimum Number of Frogs Croaking?

The challenge is correctly counting overlapping 'croak' sequences and tracking simultaneous frogs without missing partial sequences.

Can I solve this problem with simple string replacement?

No, string replacement fails when croaks overlap; you must use counting and order tracking for accuracy.

How do I know if the input string is invalid?

Check if any letter in 'croak' appears out of sequence or if total counts of 'c','r','o','a','k' are not balanced at the end.

Is there a limit to the number of frogs the string can represent?

Yes, the maximum simultaneous frogs is determined by the peak number of active croaks while processing the string.

Which pattern does this problem exemplify?

It follows the String plus Counting pattern, focusing on sequential character tracking and frequency management to find concurrency.

#1419

Medium

auto_awesomestring·结合·计数

LeetCode 题解工作台

数青蛙

给你一个字符串 croakOfFrogs ，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。要想发出蛙鸣 "croak"，青蛙必须…

字符串计数

题目描述

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。

请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

要想发出蛙鸣 "croak"，青蛙必须依序输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。

示例 1：

输入：croakOfFrogs = "croakcroak"
输出：1 
解释：一只青蛙 “呱呱” 两次

示例 2：

输入：croakOfFrogs = "crcoakroak"
输出：2 
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"

示例 3：

输入：croakOfFrogs = "croakcrook"
输出：-1
解释：给出的字符串不是 "croak" 的有效组合。

提示：

1 <= croakOfFrogs.length <= 10⁵
字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'

lightbulb

解题思路

方法一：计数 + 模拟

我们注意到，如果字符串 croakOfFrogs 是由若干有效的 "croak" 字符混合而成，那么它的长度一定是 $5$ 的倍数。因此，如果字符串的长度不是 $5$ 的倍数，可以直接返回 $-1$ 。

接下来，我们将 'c', 'r', 'o', 'a', 'k' 这 $5$ 个字母分别对应下标 $0$ 到 $4$ ，用一个长度为 $5$ 的数组 $cnt$ 记录字符串 croakOfFrogs 中每个字母出现的次数，其中 $cnt[i]$ 表示当前下标为 $i$ 的字母出现的次数。另外，我们定义一个整数变量 $x$ 表示当前未完成蛙鸣的青蛙的数目，需要的青蛙的最少数目 $ans$ 即为 $x$ 的最大值。

我们遍历字符串 croakOfFrogs 中的每个字母 $c$ ，找到 $c$ 对应的下标 $i$ ，然后将 $cnt[i]$ 加 $1$ 。接下来，根据 $i$ 值的不同，我们分别进行如下操作：

如果 $i=0$ ，那么当前有一个新的青蛙开始蛙鸣，因此令 $x$ 的值加 $1$ ，然后我们更新 $ans = \max(ans, x)$ ；
否则，如果 $cnt[i-1]=0$ ，那么表示当前没有青蛙可以发出字母 $c$ ，无法完成蛙鸣，返回 $-1$ ，否则我们令 $cnt[i-1]$ 减 $1$ 。如果 $i=4$ ，那么表示青蛙已经完成了一个蛙鸣，因此令 $x$ 的值减 $1$ 。

遍历结束后，如果 $x=0$ ，那么说明青蛙已经完成了所有的蛙鸣，返回 $ans$ ，否则返回 $-1$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(C)$ 。其中 $n$ 是字符串 croakOfFrogs 的长度；而 $C$ 是字符集的大小，本题中 $C=26$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        if len(croakOfFrogs) % 5 != 0:
            return -1
        idx = {c: i for i, c in enumerate('croak')}
        cnt = [0] * 5
        ans = x = 0
        for i in map(idx.get, croakOfFrogs):
            cnt[i] += 1
            if i == 0:
                x += 1
                ans = max(ans, x)
            else:
                if cnt[i - 1] == 0:
                    return -1
                cnt[i - 1] -= 1
                if i == 4:
                    x -= 1
        return -1 if x else ans

speed

复杂度分析

指标	值
时间	complexity is O(n) because we iterate through the string once, updating counts and checking order. Space complexity is O(1) since the hashmap only stores fixed counts for 'c','r','o','a','k'.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check for simultaneous overlapping croaks to assess string plus counting comprehension.
question_mark
Look for proper validation of sequence order to detect partial or invalid croaks.
question_mark
Ensure space usage is constant, not scaling with string length, demonstrating counting efficiency.

warning

常见陷阱

外企场景

error
Failing to track multiple frogs simultaneously, leading to undercounting.
error
Not validating order, allowing sequences like 'crook' to pass incorrectly.
error
Assuming counts reset after each 'k', missing overlapping croaks from other frogs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Input with multiple overlapping croaks requiring dynamic frog tracking.
arrow_right_alt
Strings where some croak letters are missing or out of order to test validation.
arrow_right_alt
Extended patterns with repeated croak sequences increasing concurrency requirements.

help

常见问题

外企场景

继续练习

#1400 构造 K 个回文字符串 #1370 上升下降字符串 #1366 通过投票对团队排名