题目描述

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

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

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

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

示例

示例1：

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

示例2：

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

示例2：

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

思路

• count[]来统计 "croak"的个数
• c: 0, r: 1, o: 2, a: 3, k: 4
• 每次访问到c时，维护青蛙个数 + 1
• 访问其他字符时，让前一个字符减一（保证顺序），如果前一个字符对应的count < 0 则返回-1，然后让当前字符对应的count + 1
• 访问到k时，前边的count必须也为0，维护青蛙个数 - 1
• 最后count的值必须都是0, 如果有不为0，则返回-1

如果 croakOfFrogs 是有效的蛙鸣组合，则对于每个不是 'c' 的字母，蛙鸣中的上一个字母一定在 croakOfFrogs 中已经出现。例如，当 croakOfFrogs 中存在字母 'r' 时，一定在字母 'r' 之前有字母 'c'。假设字母 'c', 'r', 'o', 'a', 'k' 对应的下标分别是 0, 1, 2, 3, 4，则当遍历到下标为 index 的字母时，进行如下操作：

TIP

如何判断字符是符合条件 —— 按照croak的顺序 当 index > 0 时，将下标 index - 1 对应的计数减 1，如果在更新计数之后，下标 index - 1 对应的计数变成负数，则 croakOfFrogs 不是有效的蛙鸣组合，返回 -1；

代码

/**
 * @param {string} croakOfFrogs
 * @return {number}
 */
var minNumberOfFrogs = function(croakOfFrogs) {
    // count[]来统计 "croak"的个数
    // c: 0, r: 1, o: 2, a: 3, k: 4
    // 每次访问到c时，维护青蛙个数 + 1
    // 访问其他字符时，让前一个字符减一（保证顺序），如果前一个字符对应的count < 0 则返回-1，然后让当前字符对应的count + 1
    // 访问到k时，前边的count必须也为0，维护青蛙个数 - 1
    // 最后count的值必须都是0, 如果有不为0，则返回-1
    if(croakOfFrogs.length % 5 != 0){
        return -1;
    }
    let count = new Array(5).fill(0);
    // 当前青蛙个数
    let curSize = 0;
    // 最大青蛙个数
    let maxSize = 0;
    // 开始遍历
    for(let i = 0; i < croakOfFrogs.length; i ++){
        let index = getIndex(croakOfFrogs.charAt(i));
        if(index == 0){
            count[index] ++;
            curSize ++;
            maxSize = Math.max(maxSize, curSize);
        }
        else{
            // 保证有序
            count[index - 1] --;
            if(count[index - 1] < 0){
                return -1;
            }
            if(index != 4){
                count[index] ++;
            }
            else{
                curSize --;
            }
        }
    }
    for(let i of count){

        if(i != 0){
            return -1;
        }
    }
    return maxSize;
    
};
// 将字符转为count数组对应的下标
var getIndex = (c) => {
    if(c == 'c'){
        return 0;
    }
    else if(c == 'r'){
        return 1;
    }
    else if(c == 'o'){
        return 2;
    }
    else if(c == 'a'){
        return 3;
    }
    else{
        return 4;
    }
};

时间复杂度分析

• 时间复杂度：O(n + |Σ|)，其中 n 是字符串 croakOfFrogs 的长度，Σ 表示字符集，这道题中的字符集包含 'c', 'r', 'o', 'a', 'k'，|Σ|=5。需要遍历字符串 croakOfFrogs 一次，以及需要遍历每个字母的计数一次。
• 空间复杂度：O(|Σ|)，其中 Σ 表示字符集，这道题中的字符集包含 'c', 'r', 'o', 'a', 'k'，|Σ|=5。空间复杂度主要为对每个字符计数的空间。