Minimum Number of Frogs Croaking — LeetCode 1419 Python Solution

The problem

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.

Example

Input

croakOfFrogs = "croakcroak"

Output

1

Explanation

One frog yelling "croak" twice.

Python solution

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        if len(croakOfFrogs) % 5 != 0:
            return -1
        idx = {c: i for i, c in enumerate('croak')}
        cnt = [0] * 5
        ans = x = 0
        for i in map(idx.get, croakOfFrogs):
            cnt[i] += 1
            if i == 0:
                x += 1
                ans = max(ans, x)
            else:
                if cnt[i - 1] == 0:
                    return -1
                cnt[i - 1] -= 1
                if i == 4:
                    x -= 1
        return -1 if x else ans

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1419. Minimum Number of Frogs Croaking is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Counting.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems