Minimum Number of Frogs Croaking

medium string counting

Problem

You are given a string croakOfFrogs formed by interleaving the croaks of several frogs (each frog says exactly "croak" in order). Return the minimum number of frogs needed to produce the string, or -1 if it is invalid.

InputcroakOfFrogs = "crcoakroak"

Output2

Two frogs are croaking concurrently: "cr" then a second frog starts before the first finishes.

croakOfFrogs

def min_number_of_frogs(s):
    order = "croak"
    idx = {c: i for i, c in enumerate(order)}
    cnt = [0] * 5
    active = best = 0
    for ch in s:
        if ch not in idx: return -1
        i = idx[ch]
        if i == 0:
            cnt[0] += 1; active += 1; best = max(best, active)
        else:
            if cnt[i - 1] == 0: return -1
            cnt[i - 1] -= 1
            if i == 4: active -= 1
            else: cnt[i] += 1
    return best if active == 0 else -1

function minNumberOfFrogs(s) {
  const order = "croak";
  const idx = { c: 0, r: 1, o: 2, a: 3, k: 4 };
  const cnt = [0, 0, 0, 0, 0];
  let active = 0, best = 0;
  for (const ch of s) {
    if (!(ch in idx)) return -1;
    const i = idx[ch];
    if (i === 0) { cnt[0]++; active++; best = Math.max(best, active); }
    else {
      if (cnt[i - 1] === 0) return -1;
      cnt[i - 1]--;
      if (i === 4) active--; else cnt[i]++;
    }
  }
  return active === 0 ? best : -1;
}

class Solution {
    public int minNumberOfFrogs(String s) {
        int[] cnt = new int[5];
        String order = "croak";
        int active = 0, best = 0;
        for (char ch : s.toCharArray()) {
            int i = order.indexOf(ch);
            if (i < 0) return -1;
            if (i == 0) { cnt[0]++; active++; best = Math.max(best, active); }
            else {
                if (cnt[i - 1] == 0) return -1;
                cnt[i - 1]--;
                if (i == 4) active--; else cnt[i]++;
            }
        }
        return active == 0 ? best : -1;
    }
}

int minNumberOfFrogs(string s) {
    string order = "croak";
    int cnt[5] = {0, 0, 0, 0, 0};
    int active = 0, best = 0;
    for (char ch : s) {
        int i = order.find(ch);
        if (i == (int)string::npos) return -1;
        if (i == 0) { cnt[0]++; active++; best = max(best, active); }
        else {
            if (cnt[i - 1] == 0) return -1;
            cnt[i - 1]--;
            if (i == 4) active--; else cnt[i]++;
        }
    }
    return active == 0 ? best : -1;
}

Explanation

Each frog must say the letters of "croak" in order. We sweep through the string once, tracking how far each in-progress croak has gotten, and the answer is the most frogs croaking at the same moment.

We keep a count cnt[i] of how many croaks are currently waiting on the letter after position i in "croak". A 'c' starts a new croak, so we bump cnt[0], increase active, and update the peak best.

For any other letter, a croak must already be sitting at the previous stage. If none is (cnt[i-1] == 0), the string is invalid and we return -1. Otherwise we move that croak forward: decrement the previous stage and either advance it (cnt[i] += 1) or, on the final 'k', finish it by decreasing active.

At the end, if any croak is still unfinished (active != 0) the string is invalid; otherwise the answer is best, the highest number of simultaneous frogs.

Example: "crcoakroak". The second 'c' arrives while the first croak is only at "cr", so two frogs overlap, and best reaches 2.

Time: O(n) Space: O(1)