Minimum Number of Frogs Croaking - Practice Coding Problems

Minimum Number of Frogs Croaking - Problem

String Counting Medium

You are given the string croakOfFrogs, which represents a combination of the string "croak" from different frogs, that is, multiple frogs can croak at the same time, so multiple "croak" are mixed.

Return the minimum number of different frogs to finish all the croaks in the given string.

A valid "croak" means a frog is printing five letters 'c', 'r', 'o', 'a', and 'k' sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of a valid "croak" return -1.

Input & Output

Example 1 — Basic Overlapping

$ Input: croakOfFrogs = "croakcroak"

› Output: 1

💡 Note: One frog can say the entire sequence: first "croak" then second "croak". Only 1 frog needed.

Example 2 — Simultaneous Frogs

$ Input: croakOfFrogs = "crcoakroak"

› Output: 2

💡 Note: Need 2 frogs: Frog1 says "c-r-o-a-k" and Frog2 says "c-r-o-a-k" with interleaved timing.

Example 3 — Invalid Sequence

$ Input: croakOfFrogs = "croakcrook"

› Output: -1

💡 Note: Contains invalid character 'o' after 'o' - not following proper croak sequence.

Constraints

1 ≤ croakOfFrogs.length ≤ 10⁵
croakOfFrogs[i] is either 'c', 'r', 'o', 'a', or 'k'

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String "crcoakroak" represents mixed croaks from multiple frogs

Frog Tracking

Track each frog's progress through c→r→o→a→k sequence

Peak Calculation

Find maximum number of frogs active simultaneously

Key Takeaway

🎯 Key Insight: Track frogs at each stage of croak sequence - the peak concurrent usage gives minimum frogs needed

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is to track frogs at each stage of the "croak" sequence using counters. As each character is processed, frogs transition between stages, and we track the maximum concurrent active frogs. Best approach is State Counter with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ State Counter Approach	O(n)	O(1)	Track count of frogs at each stage of 'croak' sequence
Brute Force State Tracking	O(5ⁿ)	O(n)	Try all possible ways to assign letters to different frogs
Stack-Based Validation	O(n)	O(n)	Use stack to validate proper nesting and sequencing of croak patterns

State Counter Approach — Algorithm Steps

Initialize counters for each stage of 'croak'
For each character, update appropriate counter
Track maximum frogs needed simultaneously

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Counters

Set up counters for each stage: c, cr, cro, croa

Process Characters

Move frogs between stages based on current character

Track Maximum

Keep track of peak concurrent frogs needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* croakOfFrogs) {
    int cCount = 0, crCount = 0, croCount = 0, croaCount = 0;
    int maxFrogs = 0;
    int len = strlen(croakOfFrogs);
    
    for (int i = 0; i < len; i++) {
        char c = croakOfFrogs[i];
        if (c == 'c') {
            cCount++;
        } else if (c == 'r') {
            if (cCount == 0) return -1;
            cCount--;
            crCount++;
        } else if (c == 'o') {
            if (crCount == 0) return -1;
            crCount--;
            croCount++;
        } else if (c == 'a') {
            if (croCount == 0) return -1;
            croCount--;
            croaCount++;
        } else if (c == 'k') {
            if (croaCount == 0) return -1;
            croaCount--;
        } else {
            return -1;
        }
        
        int currentFrogs = cCount + crCount + croCount + croaCount;
        if (currentFrogs > maxFrogs) {
            maxFrogs = currentFrogs;
        }
    }
    
    return (cCount == 0 && crCount == 0 && croCount == 0 && croaCount == 0) ? maxFrogs : -1;
}

int main() {
    char croakOfFrogs[100001];
    fgets(croakOfFrogs, sizeof(croakOfFrogs), stdin);
    croakOfFrogs[strcspn(croakOfFrogs, "\n")] = 0;
    printf("%d\n", solution(croakOfFrogs));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string, constant work per character

✓ Linear Growth

Space Complexity

O(1)

Only using fixed number of counters regardless of input size

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

State Counter Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler