数青蛙

难度: Medium

给你一个字符串 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'

Submission

运行时间: 76 ms

内存: 16.4 MB

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        c,r,o,a,k = 0,0,0,0,0
        ret = 0
        for i in croakOfFrogs:
            if i == 'c':
                c += 1
                ret = max(c-k,ret)
            elif c > r and i == 'r':
                r += 1
            elif r > o and i == 'o':
                o += 1
            elif o > a and i == 'a':
                a += 1
            elif a > k and i == 'k':
                k += 1
            else:return -1
        return ret if c==r and c==o and c==a and c==k else -1

Explain

该题解通过模拟青蛙发出的声音的顺序，使用五个变量c, r, o, a, k来跟踪每个字符'c', 'r', 'o', 'a', 'k'出现的次数。变量ret用于记录同时叫声所需的最大青蛙数量。遍历字符串中的每一个字符，更新相应字符的计数器，确保字符的顺序符合'croak'的顺序。如果当前字符为'c', 则增加c的计数，同时更新ret为当前活跃的青蛙数量，即c-k的值。对于'r', 'o', 'a', 'k'的处理，确保前一个字符的计数器大于当前字符的计数器，这样才能保证字符的顺序。最后，如果所有字符的计数相等，表示所有'croak'都是完整的，则返回ret；否则，如果有不匹配的，返回-1。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        c, r, o, a, k = 0, 0, 0, 0, 0  # 初始化字符计数器
        ret = 0  # 最大同时叫声的青蛙数量
        for i in croakOfFrogs:
            if i == 'c':
                c += 1  # 增加c的计数
                ret = max(c-k, ret)  # 更新最大青蛙数量
            elif c > r and i == 'r':
                r += 1  # 增加r的计数
            elif r > o and i == 'o':
                o += 1  # 增加o的计数
            elif o > a and i == 'a':
                a += 1  # 增加a的计数
            elif a > k and i == 'k':
                k += 1  # 增加k的计数
            else:
                return -1  # 如果顺序错误或出现无法处理的字符，返回-1
        return ret if c == r and c == o and c == a and c == k else -1  # 检查是否所有计数相等

Explore

在处理字符'r', 'o', 'a', 'k'时，代码分别检查了前一个字符的计数器是否大于当前字符的计数器。例如，当i为'r'时，代码中有一个条件判断`c > r`，只有当c（即前一个字符'c'的计数器）大于r（即当前字符'r'的计数器）时，才会将r的计数器增加。这样的逻辑确保了字符的顺序符合'croak'这一顺序，因为每个'croak'必须以'c'开始，依次经过'r', 'o', 'a'到'k'。

是的，如果在处理字符串时遇到顺序错误或遇到了非'croak'字符，代码会直接返回-1。这意味着一旦检测到错误，不仅当前字符处理失败，整个字符串都被认为是无效的，因为它不满足题目要求的每个'croak'声音完整且正确的顺序。因此，无论之前的字符是否正确，整个字符串都不再有效。

在每次遇到'c'字符时更新ret为c-k的值主要是为了跟踪同时发出'croak'声音的最大青蛙数量。在这里，c代表开始一个新的'croak'的次数，而k代表完成'croak'声音的次数。c-k因此表示当前正在发出'croak'声音但尚未完成的青蛙数量。通过更新ret为这个值的最大值，我们能确保ret始终保持为同时发出'croak'声音的最大青蛙数量，这对解决问题至关重要。

代码中通过在处理每个字符时设置条件判断来处理潜在的非'croak'字符。如果遇到的字符不是'c', 'r', 'o', 'a', 或 'k'，或者它的顺序不正确（即前一个字符的计数器不大于当前字符的计数器），则代码将返回-1。这样的设计直接使任何包含非'croak'字符的字符串或顺序错误的情况被识别为无效，终止进一步的处理。