1419. 数青蛙

🟠   🔖  字符串 计数  🔗 力扣 LeetCode

题目

You are 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 croaks in the given string.

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

The second frog could yell later "crc oakroak ".

Example 3:

Input: croakOfFrogs = "croakcrook"

Output: -1

Explanation: The given string is an invalid combination of "croak**"** from different frogs.

Constraints:

• 1 <= croakOfFrogs.length <= 10^5
• croakOfFrogs is either 'c', 'r', 'o', 'a', or 'k'.

题目大意

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

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

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

示例 1：

输入： croakOfFrogs = "croakcroak"

输出： 1

解释： 一只青蛙 “呱呱” 两次

示例 2：

输入： croakOfFrogs = "crcoakroak"

输出： 2

解释： 最少需要两只青蛙，“呱呱” 声用黑体标注

第一只青蛙 "cr coak roak"

第二只青蛙 "crc oakroak "

示例 3：

输入： croakOfFrogs = "croakcrook"

输出： -1

解释： 给出的字符串不是 "croak" 的有效组合。

提示：

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

解题思路

1. 维护五个计数器，分别表示有多少个字符 'c'、'r'、'o'、'a' 和 'k'。这五个字符必须按照 "croak" 的顺序出现，所以每当一个字符出现时，要检查它的前置字符是否有足够的数量。

2. 使用变量 frogs 和 maxFrogs 来跟踪在处理过程中，正在发声的青蛙数量及其最大值。

3. 遍历字符串

• 每次遇到 'c' 时，意味着有一只新的青蛙开始发声，frogs++；
• 当遇到 'k' 时，表示一次完整的 "croak" 结束，frogs--；
• 遇到每个字符都需要检查相应的前置字符是否有足够的数量；

3. 边界情况

• 如果在处理过程中，某个字符的数量超过了它前一个字符的数量，说明字符顺序错乱，返回 -1。
• 最后，如果 frogs 没有被正确清零，说明还有未完整结束的发声，也返回 -1。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。只需遍历字符串一次，更新字符计数器。
• 空间复杂度：O(1)，只使用常量的额外空间来存储字符计数器和变量。

代码

/**
 * @param {string} croakOfFrogs
 * @return {number}
 */
var minNumberOfFrogs = function (croakOfFrogs) {
	let count = { c: 0, r: 0, o: 0, a: 0, k: 0 };
	let frogs = 0,
		maxFrogs = 0;
	for (let char of croakOfFrogs) {
		count[char]++;
		if (char == 'c') {
			frogs++;
			maxFrogs = Math.max(maxFrogs, frogs);
		} else if (char == 'k') {
			frogs--;
		}

		if (
			!(
				count['c'] >= count['r'] &&
				count['r'] >= count['o'] &&
				count['o'] >= count['a'] &&
				count['a'] >= count['k']
			)
		) {
			return -1;
		}
	}
	return frogs == 0 ? maxFrogs : -1;
};

相关题目

题号	标题	题解	标签	难度
2406	将区间分为最少组数	[✓]	贪心 数组 双指针 3+