Medium

Quiz

#1419 Minimum Number of Frogs Croaking

APPROACH

The string croakOfFrogs is formed by interleaving multiple instances of the word "croak", one per frog, with frogs potentially croaking simultaneously. Each frog must emit the full sequence 'c' -> 'r' -> 'o' -> 'a' -> 'k'. Return the minimum number of frogs required to produce the given string, or -1 if the string is not a valid interleaving of complete croaks.

Example 1:

Input: croakOfFrogs = "croakcroak"

Output: 1

Explanation: One frog yelling "croak" twice.

Example 2:

Input: croakOfFrogs = "crcoakroak"

Output: 2

Explanation: The minimum number of frogs is two.

The first frog could yell "crcoakroak".

The second frog could yell later "crcoakroak".

Example 3:

Input: croakOfFrogs = "croakcrook"

Output: -1

Explanation: The given string is an invalid combination of "croak" from different frogs.

1 of 4

1:00

What is the optimal approach for this problem?