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

---

这题有点意思，比赛结束前3分钟我才AC了。。。

给定一个字符串，表示青蛙咳嗽的字符串。青蛙每咳一声，会发出croak这一串字符。现在有多个青蛙同时咳嗽，则多个croak会被打乱输出，可以想象下多线程输出到同一个文件时，顺序是乱的。

问一个咳嗽字符串最少可以由几个青蛙产生的，注意青蛙咳完一声后可以接着咳。

我一开始的做法比较暴力，对于每个字符，检查它是否属于之前某个青蛙的咳嗽字符串中，如果属于则放入，不属于且是c的话，则新开一个咳嗽字符串。完整代码如下：

class Solution {
public:
	int minNumberOfFrogs(string croakOfFrogs) {
		map<char, char> pre = { {'r','c'},{'o','r'},{'a','o'},{'k','a'} };
		vector<vector<char>> ans;
		map<char, int> count;
		for (int i = 0; i < croakOfFrogs.size(); ++i) {
			int letter = croakOfFrogs[i];
			++count[letter];
			if (!(count['c'] >= count['r'] && count['r'] >= count['o'] && count['o'] >= count['a'] && count['a'] >= count['k']))return -1;
			if (letter == 'c') {
				if (ans.empty()) {
					ans.push_back({ 'c' });
				}
				else {
					bool found = false;
					for (int j = 0; j < ans.size(); ++j) {
						if (ans[j].empty()) {
							ans[j].push_back('c');
							found = true;
							break;
						}
					}
					if (!found) {
						ans.push_back({ 'c' });
					}
				}
			}
			else {
				if (ans.empty())return -1;
				else {
					bool found = false;
					for (int j = 0; j < ans.size(); ++j) {
						if (!ans[j].empty() && ans[j].back() == pre[letter]) {
							ans[j].push_back(letter);
							found = true;
							if (letter == 'k')ans[j].clear();
							break;
						}
					}
					if (!found)return -1;
				}
			}
		}

		for (int j = 0; j < ans.size(); ++j) {
			if (!ans[j].empty())return -1;
		}

		return ans.size();
	}
};

这个解法TLE了，最后几个测试用例过不了。这个解法的问题是对每个字符都要遍历之前所有青蛙的咳嗽数组，太耗时了。

后来想到一种O(n)解法。因为咳嗽字符串是croak，在遍历的过程中，只要满足出现次数c>=r>=o>=a>=k就是合法的。然后设定一个free变量，记录当前有多少只青蛙是之前咳嗽结束了，已经空闲下来，可以进行下一轮咳嗽了。如果来一个c，且有free的话，则拿一个free的青蛙进行咳嗽，否则新开一个青蛙。如果新来一个k，则说明这个青蛙咳嗽结束，多一个空闲青蛙，free++。

完整代码如下：

class Solution {
public:
	int minNumberOfFrogs(string croakOfFrogs) {
		int n = croakOfFrogs.size();
		map<char, int> count;
		int free = 0, ans = 0;
		for (int i = 0; i < croakOfFrogs.size(); ++i) {
			char letter = croakOfFrogs[i];
			++count[letter];
			if (!(count['c'] >= count['r'] && count['r'] >= count['o'] && count['o'] >= count['a'] && count['a'] >= count['k']))return -1;
			if (letter == 'c'&&free == 0) {
				++ans;
			}
			else if (letter == 'c'&&free > 0) {
				--free;
			}
			else if (letter == 'k') {
				++free;
			}
		}
		if (count['c'] != count['k'])return -1;
		return ans;
	}
};

本代码提交AC，用时388MS。