Question

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

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.

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.

Constraints:

1 <= croakOfFrogs.length <= 10⁵
croakOfFrogs is either '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;
        }
    }
}


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

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        int c = 0, r = 0, o = 0, a = 0, k = 0;
        int ans = 0;
        for (char ch : croakOfFrogs.toCharArray()) {
            if (ch == 'c') {
                ++c;
                if (k > 0) {
                    --k;
                } else {
                    ++ans;
                }
            } else if (ch == 'r') {
                ++r;
                --c;
            } else if (ch == 'o') {
                ++o;
                --r;
            } else if (ch == 'a') {
                ++a;
                --o;
            } else {
                ++k;
                --a;
            }
            if (c < 0 || r < 0 || o < 0 || a < 0) {
                return -1;
            }
        }
        return c == 0 && r == 0 && o == 0 && a == 0 ? ans : -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:
        if not croakOfFrogs:
            return -1
        
        curr, res = 0, 0
        c, r, o, a, k = 0, 0, 0, 0, 0

        for each in croakOfFrogs:
            if each == 'c':
                c += 1
                curr += 1
            elif each == 'r':
                r += 1
            elif each == 'o':
                o += 1
            elif each == 'a':
                a += 1
            else:
                k += 1
                curr -= 1
            
            res = max(res, curr)
            if c < r or r < o or o < a or a < k:
                return -1
            
        if c == r == o == a == k:
            return res
        
        return -1

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

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

func minNumberOfFrogs(croakOfFrogs string) int {
	c, r, o, a, k, ans := 0, 0, 0, 0, 0, 0
	for i := range croakOfFrogs {
		ch := croakOfFrogs[i]
		if ch == 'c' {
			c++
			if k > 0 {
				k--
			} else {
				ans++
			}
		} else if ch == 'r' {
			r++
			c--
		} else if ch == 'o' {
			o++
			r--
		} else if ch == 'a' {
			a++
			o--
		} else {
			k++
			a--
		}
		if c < 0 || r < 0 || o < 0 || a < 0 {
			return -1
		}
	}
	if c == 0 && r == 0 && o == 0 && a == 0 {
		return ans
	}
	return -1
}

function minNumberOfFrogs(croakOfFrogs: string): number {
    const n = croakOfFrogs.length;
    if (n % 5 !== 0) {
        return -1;
    }
    const idx = (c: string): number => 'croak'.indexOf(c);
    const cnt: number[] = [0, 0, 0, 0, 0];
    let ans = 0;
    let x = 0;
    for (const c of croakOfFrogs) {
        const i = idx(c);
        ++cnt[i];
        if (i === 0) {
            ans = Math.max(ans, ++x);
        } else {
            if (--cnt[i - 1] < 0) {
                return -1;
            }
            if (i === 4) {
                --x;
            }
        }
    }
    return x > 0 ? -1 : ans;
}

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