We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Frogs Croaking

Difficulty: Medium

Problem Description

You are given the string croakOfFrogs, which represents a combination of the string "croak" from different frogs. Return the minimum number of different frogs to finish all the croaks in the given string. If the given string is not a combination of a valid "croak", return -1.

Key Insights

  • A valid "croak" consists of the characters 'c', 'r', 'o', 'a', 'k' in that specific order.
  • We need to track the number of frogs croaking at any given moment.
  • If at any point the sequence of croaks is invalid (e.g., more 'r's than 'c's), we should return -1.
  • The maximum number of concurrent croakers will give us the minimum number of frogs required.

Space and Time Complexity

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

Solution

To solve this problem, we can use a counting approach to track the number of occurrences of each character in the sequence "croak". We will maintain a count for each of the characters in the order they appear. We will also check for any invalid sequences by ensuring the counts of each character follow the correct progression:

  • count['c'] should be greater than or equal to count['r']
  • count['r'] should be greater than or equal to count['o']
  • count['o'] should be greater than or equal to count['a']
  • count['a'] should be greater than or equal to count['k'] Finally, we will return the maximum concurrent frogs croaking at any time.

Code Solutions

def minNumberOfFrogs(croakOfFrogs: str) -> int:
    croak_count = {'c': 0, 'r': 0, 'o': 0, 'a': 0, 'k': 0}
    max_frogs = 0
    frogs = 0

    for char in croakOfFrogs:
        if char == 'c':
            frogs += 1
            croak_count['c'] += 1
        elif char == 'r':
            if croak_count['c'] <= croak_count['r']:
                return -1
            croak_count['r'] += 1
        elif char == 'o':
            if croak_count['r'] <= croak_count['o']:
                return -1
            croak_count['o'] += 1
        elif char == 'a':
            if croak_count['o'] <= croak_count['a']:
                return -1
            croak_count['a'] += 1
        elif char == 'k':
            if croak_count['a'] <= croak_count['k']:
                return -1
            croak_count['k'] += 1
            frogs -= 1  # A frog finished croaking
        max_frogs = max(max_frogs, frogs)

    if croak_count['c'] != croak_count['r'] or croak_count['r'] != croak_count['o'] or croak_count['o'] != croak_count['a'] or croak_count['a'] != croak_count['k']:
        return -1

    return max_frogs
← Back to All Questions