Minimum Number of Frogs Croaking

Medium
645.

Minimum Number of Frogs Croaking

Minimum Number of Frogs Croaking is a medium coding problem on strings, greedy and counting, asked in Amazon, Google and Samsung interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} croakOfFrogs
 * @return {number}
 */
var minNumberOfFrogs = function(croakOfFrogs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Frogs Croaking — Problem & Solution

Minimum Number of Frogs Croaking solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Number of Frogs Croaking is a medium coding problem on strings, greedy and counting, asked in Amazon, Google and Samsung interviews.

  • 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.

Hints for Minimum Number of Frogs Croaking

  1. Hint 1

    Count how many frogs are mid-croak at each moment; the peak is the answer.

  2. Hint 2

    A 'c' starts a croak and a 'k' finishes one.

  3. Hint 3

    Validity is a prefix condition: at every moment the count of each letter must not exceed the count of the letter before it in "croak".

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

Java

public static int minNumberOfFrogs(String croakOfFrogs) {
    String order = "croak";
    int[] count = new int[5];
    int active = 0, best = 0;
    for (int i = 0; i < croakOfFrogs.length(); i++) {
        int 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 (int j = 1; j < 5; j++) {
        if (count[j] != count[0]) return -1;
    }
    return count[0] == 0 ? 0 : best;
}

C++

int minNumberOfFrogs(string croakOfFrogs) {
    string order = "croak";
    vector<int> count(5, 0);
    int active = 0, best = 0;
    for (char ch : croakOfFrogs) {
        size_t pos = order.find(ch);
        if (pos == string::npos) return -1;
        int idx = (int) pos;
        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 (int j = 1; j < 5; j++) {
        if (count[j] != count[0]) return -1;
    }
    return count[0] == 0 ? 0 : 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms