Get started

Minimum Number of Frogs Croaking — Medium Problem & Solution

You hear a recording croakOfFrogs of several frogs croaking at once.

  • Difficulty: Medium
  • Topics: Strings, Greedy, Counting
  • Asked at: Amazon, Google, Samsung
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You hear a recording croakOfFrogs of several frogs croaking at once. A single croak is the letters c, r, o, a, k in that order, and a frog must finish one croak before starting another. Frogs may overlap freely.

Return the minimum number of frogs that could have produced the recording, or -1 if it is not a valid interleaving of complete croaks.

Example 1

Input: s = "croakcroak"
Output: 1
Explanation: One frog croaking twice in a row.

Example 2

Input: s = "crcoakroak"
Output: 2
Explanation: Two frogs overlapping.

Example 3

Input: s = "croakcrook"
Output: -1
Explanation: The second croak is misspelled.

Constraints

  • 1 <= croakOfFrogs.length <= 100000
  • croakOfFrogs consists of the letters c, r, o, a and k.

How to solve Minimum Number of Frogs Croaking

Track the running tally of each of the five letters. A frog is mid-croak between its 'c' and its 'k', so the number of concurrent frogs is the number of 'c's not yet matched by a 'k' — and the peak of that is the minimum fleet size.

Approach

  1. Keep count[0..4] for c, r, o, a, k.
  2. On 'c', increment the active count and update the peak.
  3. On any other letter at index i, reject if its tally would exceed the tally of letter i - 1; on 'k', decrement the active count.
  4. After the sweep, reject unless all five tallies are equal — otherwise some croak is unfinished.

Why it works

A letter appearing more often than its predecessor means some frog sang out of order, so the prefix inequality is exactly validity. Frogs can be reused the instant they finish, so the peak of concurrent croaks is both necessary (that many sounded at once) and sufficient (schedule each new 'c' on any idle frog).

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Checking only the final tallies misses "crcoakroak"-style reorderings that go wrong mid-string.
  • Forgetting the end-of-string equality check accepts a recording that stops mid-croak.
  • Reporting the number of 'c's instead of the peak overcounts sequential croaks by the same frog.

Reference solution

Python

def minNumberOfFrogs(croakOfFrogs: str) -> int:
    order = "croak"
    count = [0] * 5
    active = 0
    best = 0
    for ch in croakOfFrogs:
        idx = order.find(ch)
        if idx < 0:
            return -1
        count[idx] += 1
        if idx == 0:
            active += 1
            best = max(best, active)
        else:
            if count[idx] > count[idx - 1]:
                return -1
            if idx == 4:
                active -= 1
    if any(count[i] != count[0] for i in range(1, 5)):
        return -1
    return 0 if count[0] == 0 else best

JavaScript

var minNumberOfFrogs = function(croakOfFrogs) {
    var order = "croak";
    var count = [0, 0, 0, 0, 0];
    var active = 0, best = 0;
    for (var i = 0; i < croakOfFrogs.length; i++) {
        var idx = order.indexOf(croakOfFrogs.charAt(i));
        if (idx < 0) return -1;
        count[idx]++;
        if (idx === 0) {
            active++;
            if (active > best) best = active;
        } else {
            if (count[idx] > count[idx - 1]) return -1;
            if (idx === 4) active--;
        }
    }
    for (var j = 1; j < 5; j++) {
        if (count[j] !== count[0]) return -1;
    }
    return count[0] === 0 ? 0 : best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue