Minimum Number of Frogs Croaking

MediumStringssimulation

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A frog croaks by producing the letters 'c', 'r', 'o', 'a', 'k' in exactly that order. Several frogs may croak at the same time, so their letters can be interleaved in the recording croakOfFrogs. A frog that finishes a croak may start another one later. Every letter of the recording must belong to some complete croak. Return the minimum number of distinct frogs that could have produced the recording. If the recording cannot be split into complete croaks (a letter arrives out of order, or some croak is left unfinished), return -1.

Examples

Input: croakOfFrogs = "croakcroak"
Output: 1
One frog croaks twice in a row.
Input: croakOfFrogs = "crcoakroak"
Output: 2
The second 'c' arrives while the first frog is mid-croak, so a second frog is needed.
Input: croakOfFrogs = "croakcrook"
Output: -1
In the second croak an extra 'o' arrives when no frog is waiting to say 'o', so the recording is invalid.

Constraints

  • 1 <= croakOfFrogs.length <= 10^5
  • croakOfFrogs consists only of the letters 'c', 'r', 'o', 'a', 'k'

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More simulation problems