Problem

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.

Examples

Example 1

1
2
3

Input: croakOfFrogs = "croakcroak"
Output: 1 
Explanation: One frog yelling "croak**"** twice.

Example 2

1
2
3
4
5

Input: croakOfFrogs = "crcoakroak"
Output: 2 
Explanation: The minimum number of frogs is two. 
The first frog could yell "**cr** c**oak** roak".
The second frog could yell later "cr**c** oak**roak** ".

Example 3

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

Solution

Method 1 – Counting State Transitions

Intuition

Track the number of frogs at each stage of croak. For each character, increment the count for that stage and decrement the previous stage. The answer is the maximum number of frogs simultaneously croaking. If the sequence is invalid, return -1.

Approach

  1. Map ‘c’,‘r’,‘o’,‘a’,‘k’ to stages 0-4.
  2. For each character, increment its stage, decrement previous stage.
  3. If any stage goes negative, return -1.
  4. At each ‘c’, increment frogs; at each ‘k’, decrement frogs.
  5. Track the maximum frogs needed.
  6. At the end, all stages except 0 must be zero.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <string>
using namespace std;
class Solution {
public:
    int minNumberOfFrogs(string s) {
        int cnt[5] = {}, frogs = 0, maxFrogs = 0;
        string croak = "croak";
        for (char ch : s) {
            int idx = croak.find(ch);
            if (idx == 0) { ++frogs; maxFrogs = max(maxFrogs, frogs); }
            else if (--cnt[idx-1] < 0) return -1;
            if (idx == 4) --frogs;
            ++cnt[idx];
        }
        for (int i = 0; i < 4; ++i) if (cnt[i]) return -1;
        return maxFrogs;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func minNumberOfFrogs(s string) int {
    cnt := make([]int, 5)
    croak := "croak"
    frogs, maxFrogs := 0, 0
    for _, ch := range s {
        idx := strings.IndexByte(croak, byte(ch))
        if idx == 0 {
            frogs++
            if frogs > maxFrogs { maxFrogs = frogs }
        } else {
            cnt[idx-1]--
            if cnt[idx-1] < 0 { return -1 }
        }
        if idx == 4 { frogs-- }
        cnt[idx]++
    }
    for i := 0; i < 4; i++ { if cnt[i] != 0 { return -1 } }
    return maxFrogs
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int minNumberOfFrogs(String s) {
        int[] cnt = new int[5];
        String croak = "croak";
        int frogs = 0, maxFrogs = 0;
        for (char ch : s.toCharArray()) {
            int idx = croak.indexOf(ch);
            if (idx == 0) { frogs++; maxFrogs = Math.max(maxFrogs, frogs); }
            else if (--cnt[idx-1] < 0) return -1;
            if (idx == 4) frogs--;
            cnt[idx]++;
        }
        for (int i = 0; i < 4; ++i) if (cnt[i] != 0) return -1;
        return maxFrogs;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun minNumberOfFrogs(s: String): Int {
        val cnt = IntArray(5)
        val croak = "croak"
        var frogs = 0; var maxFrogs = 0
        for (ch in s) {
            val idx = croak.indexOf(ch)
            if (idx == 0) { frogs++; maxFrogs = maxOf(maxFrogs, frogs) }
            else if (--cnt[idx-1] < 0) return -1
            if (idx == 4) frogs--
            cnt[idx]++
        }
        for (i in 0..3) if (cnt[i] != 0) return -1
        return maxFrogs
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def minNumberOfFrogs(self, s: str) -> int:
        croak = 'croak'
        cnt = [0]*5
        frogs = maxFrogs = 0
        for ch in s:
            idx = croak.index(ch)
            if idx == 0:
                frogs += 1
                maxFrogs = max(maxFrogs, frogs)
            else:
                cnt[idx-1] -= 1
                if cnt[idx-1] < 0:
                    return -1
            if idx == 4:
                frogs -= 1
            cnt[idx] += 1
        if any(cnt[i] for i in range(4)):
            return -1
        return maxFrogs
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn min_number_of_frogs(s: String) -> i32 {
        let croak = ['c','r','o','a','k'];
        let mut cnt = [0; 5];
        let (mut frogs, mut max_frogs) = (0, 0);
        for ch in s.chars() {
            let idx = croak.iter().position(|&x| x == ch).unwrap();
            if idx == 0 { frogs += 1; max_frogs = max_frogs.max(frogs); }
            else {
                cnt[idx-1] -= 1;
                if cnt[idx-1] < 0 { return -1; }
            }
            if idx == 4 { frogs -= 1; }
            cnt[idx] += 1;
        }
        if cnt[..4].iter().any(|&x| x != 0) { return -1; }
        max_frogs
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    minNumberOfFrogs(s: string): number {
        const croak = 'croak';
        const cnt = Array(5).fill(0);
        let frogs = 0, maxFrogs = 0;
        for (const ch of s) {
            const idx = croak.indexOf(ch);
            if (idx === 0) { frogs++; maxFrogs = Math.max(maxFrogs, frogs); }
            else if (--cnt[idx-1] < 0) return -1;
            if (idx === 4) frogs--;
            cnt[idx]++;
        }
        if (cnt.slice(0,4).some(x => x !== 0)) return -1;
        return maxFrogs;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — n = length of s.
  • 🧺 Space complexity: O(1) — only 5 counters.