LeetCode - 1419 数青蛙

题目来源

1419. 数青蛙 - 力扣（LeetCode）

题目描述

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

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

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

示例

提示

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

题目解析

本题要求至少几只青蛙才能产生用例叫声。

其实这个问题可以改为：找出最多只青蛙同时叫的情况。

同时叫，意味着，一只青蛙未叫完的过程中，又有其他青蛙开始叫。比如

crcoakroak

在红色呱声未叫完前，又有一个呱声叫了起来，因此至少要有两个青蛙。

croakcroak

而上面这个红色呱声叫的过程中，没有新呱声产生，因此可能只有一个青蛙。

因此，我们只需要统计相邻‘c’和'k'之间，至多的‘c’个数，即为至少青蛙数。

但是，由于叫声存在不合法的情况，比如croakcrook，其中字符虽然都是呱声字符，但是并不能形成呱声。我们检查是否存在这种情况，检查逻辑是：

由于呱声，必然是先产生c，再产生r，再产生o，再产生a，最后产生k，因此无论是一只青蛙叫，还是多只青蛙同时叫，croakOfFrogs 输入的叫声字符串的任意索引位置，都满足，出现过的c的个数 >= r的个数 >= o的个数 >= a的个数 >= k的个数。

因此，如果某一个索引位置，统计的字符个数不满足上面条件，则有非法呱声。

另外，当我们遍历完所有字符后，仅仅满足上面条件还是不够的，我们需要考虑下面情况：

crcoakro

即，包含不完整的呱声，此时依旧满足上面条件，但是不合法，即合法的呱声字符串，最终统计的各个字符的数量是要相等的。

算法源码

/**
 * @param {string} croakOfFrogs
 * @return {number}
 */
var minNumberOfFrogs = function(croakOfFrogs) {
    let c, r, o, a, k;
    c = r = o = a = k = 0;
 
    let count, max;
    count = max = 0;
 
    for(let char of croakOfFrogs) {
        switch(char) {
            case 'c': 
                c++;
                count++;
                break;
            case 'r': 
                r++;
                break;
            case 'o': 
                o++;
                break;
            case 'a': 
                a++;
                break;
            case 'k': 
                k++;
                count--;
                break;
        }
 
        if(c >= r && r >= o && o >= a && a >= k) {
            max = Math.max(max, count)
        } else {
            return -1
        }
    }
 
    if(r === c && o === c && a === c && k === c) {
        return max
    } else {
        return -1
    }
};