1419. 数青蛙

江无回头浪，人无再少年。年华若虚度，老来恨不浅。时光容易逝，岁月莫消遣。碌碌而无为，生命不值钱。

LC每日一题，参考1419. 数青蛙，难度分1690。

题目

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

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

输入：croakOfFrogs = "crcoakroak"
输出：2 
解释：最少需要两只青蛙

解题思路

• 统计词频：需要找规律,对于叫声有顺序和数量的规则限制,同时统计当前遇到c的数量-当前遇到的k的数量即为最小青蛙数。

统计词频

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        if(croakOfFrogs.length() %5 != 0) return -1;
        int ans = 0;
        //判断c字符数量 和 k字符数量前后关系 最小即为最大的c-k区间(cCount-kCount)
        int cCount = 0,rCount = 0,oCount = 0,aCount = 0,kCount = 0;
        for(char c : croakOfFrogs.toCharArray()) {
            if(c == 'c') ans = Math.max(ans,++cCount-kCount);
            else if(c == 'r') rCount++;
            else if(c == 'o') oCount++;
            else if(c == 'a') aCount++;
            else if(c == 'k') kCount++;
            //判断先后关系
            if(cCount < rCount || rCount < oCount || 
               oCount < aCount || aCount < kCount) return -1;
        }
        //判断数量关系
        if(cCount != rCount || rCount != oCount || 
           oCount != aCount || aCount != kCount) return -1;
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)，遍历字符串s一次,n为字符串s长度。
• 空间复杂度：O(1)，只使用常数(5)个变量空间。