Question

Formatted question description: https://leetcode.ca/all/1419.html

 1419. Minimum Number of Frogs Croaking

 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 croak in the given string.

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

 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.

 Example 4:

 Input: croakOfFrogs = "croakcroa"
 Output: -1

 Constraints:
     1 <= croakOfFrogs.length <= 10^5
     All characters in the string are: 'c', 'r', 'o', 'a' or 'k'.

Algorithm

The idea is scanning lines, but the step of judging the croak is greatly simplified. Every time we encounter the first ‘c’ and the last ‘k’. Directly subtract one from the previous character number of the current character.

If the previous digit is less than 0 after subtracting one, it means that there is no character before the current digit that matches it.

Assuming that our input is “crok”, when we traverse to k, the position of its previous ‘a’ is 0, indicating that we have one more string k. So there is no way to match.

The rest is the same as the scan line. When we encounter a new c, we add a frog and when we encounter k. We reduce a frog.

[c, r, o, a, k], the number of characters at any time, in this order not ascending
The final quantity must be equal
The maximum of 5 characters at any time is the number of frogs needed
If 5 characters are full of a frog, subtract it, and you can reuse the frog later.

Code

public class Minimum_Number_of_Frogs_Croaking {

    class Solution {
        public int minNumberOfFrogs(String croakOfFrogs) {

            if (croakOfFrogs == null) {
                return -1;
            }

            char[] charArray = croakOfFrogs.toCharArray();
            int curr = 0;
            int res = 0;
            int c = 0, r = 0, o = 0, a = 0, k = 0 ;

            for (char each : charArray) {
                if (each == 'c') {
                    c++;
                    curr++;
                } else if (each == 'r') {
                    r++;
                } else if (each == 'o') {
                    o++;
                } else if (each == 'a') {
                    a++;
                } else {
                    k++;
                    curr--;
                }
                res = Math.max(res, curr);
                if (c < r || r < o || o < a || a < k) { // satifiy all, or else false
                    return -1;
                }
            }

            if((c == r) && (r == o ) && ( o == a) &&  (a == k)) {
                return res;
            }

            return -1;
        }
    }
}

// OJ: https://leetcode.com/problems/minimum-number-of-frogs-croaking/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minNumberOfFrogs(string s) {
        string t = "croak";
        vector<int> cnt(5);
        int ans = 0, cur = 0;
        for (char c : s) {
            int n = t.find(c);
            if (n == string::npos) return -1;
            if (n != 0 && --cnt[n - 1] < 0) return -1;
            ++cnt[n];
            if (n == 0) ++cur;
            else if (n == 4) --cur;
            ans = max(ans, cur);
        }
        return cur ? -1 : ans;
    }
};

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        c = r = o = a = k = ans = 0
        for ch in croakOfFrogs:
            if ch == 'c':
                c += 1
                if k > 0:
                    k -= 1
                else:
                    ans += 1
            elif ch == 'r':
                r += 1
                c -= 1
            elif ch == 'o':
                o += 1
                r -= 1
            elif ch == 'a':
                a += 1
                o -= 1
            else:
                k += 1
                a -= 1
            if c < 0 or r < 0 or o < 0 or a < 0:
                return -1
        return -1 if c != 0 or r != 0 or o != 0 or a != 0 else ans

############

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        count = collections.Counter()
        prev = {"k" :  "a", "a": "o", "o": "r", "r" : "c"}
        res = 0
        for c in croakOfFrogs:
            if c == "c":
                count[c] += 1
            else:
                if count[prev[c]] > 0:
                    if c != "k":
                        count[c] += 1
                    count[prev[c]] -= 1
                else:
                    return -1
            res = max(res, sum(count.values()))
        return res if sum(count.values()) == 0 else -1

1419 - Minimum Number of Frogs Croaking

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions