Leetcode: 1419. Minimum Number of Frogs Croaking

• Pattern: Optimization problem to find minimum/maximum number of X to cover Y.
• Pattern: Problem allows an operation/agent/thing to be used multiple times.

• Can we solve the problem using a greedy approach?

The fact that one frog can croak multiple times means that two independent croaks can be performed by the same frog. For example, one frog can produce "croakcroak" while two frogs are required to produce "crcroakoakcroak" ("aabbbbbaaaaaaaa" or "aabbbbbaaabbbbb" where \(a\) and \(b\) represents two frogs). Thus, we can postpone the decision to add one frog to the answer iff all other frogs are in busy croaking. Doing so, the algorithm is making a locally optimal choice (Greedy algorithm).

The solution consists on iterating over input letters counting how many frogs are busy on each letter "c", "r", "o", "a" and "k". If the next letter is a "c", we only add a new frog if at least one frog finished a "k" letter. After processing all letters, the number of frogs on the letter "k" is the final answer iff there is no frog stuck on any other letter. Time complexity is \(O(n)\) and space is \(O(1)\).

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        c = Counter()
        p = {a: b for a, b in zip("roak", "croak")}
        for x in croakOfFrogs:
            c[x] += 1
            if x == "c":
                c["k"] -= 1 if c["k"] else 0
            elif c[p[x]]:
                c[p[x]] -= 1
            else:
                return -1
        return c["k"] if c["k"] == c.total() else -1