1419. Minimum Number of Frogs Croaking

Description

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'.

Solutions

The concept revolves around simplifying the process of identifying the sequence “croak” within a given string. This method focuses on tracking each occurrence of the characters in the sequence from ‘c’ to ‘k’.

Strategy Overview

The approach involves scanning through the string and applying a straightforward rule for detecting the “croak” sound sequence. The core principle is to decrement the count of the previous character in the sequence whenever the current character is encountered.

Character Count Adjustment: Upon encountering a character, reduce the count of its immediate predecessor in the “croak” sequence by one.
Validity Check: If the count of the predecessor character becomes negative, it indicates a mismatch or an incomplete sequence. For example, given the input “crok”, by the time we reach ‘k’, the absence of ‘a’ before it (since ‘a’s count would be 0) signifies an unmatched ‘k’, making the sequence invalid.
Counting Frogs:
- When a new ‘c’ is found, it implies the start of a new “croak” sequence, and thus, a new frog is needed.
- Conversely, upon encountering a ‘k’, it signifies the completion of a “croak” sequence, allowing for a decrement in the frog count, essentially indicating that the frog has finished croaking and is available for reuse.

Key Points

Character Count Tracking: Maintain counts of [c, r, o, a, k] characters. At any given point, the sequence of counts should not be in ascending order, ensuring the “croak” sequence is followed correctly.
Equality of Final Counts: All character counts must be equal at the end, confirming that each “croak” sequence initiated has been completed.
Frog Requirement: The maximum count among the 5 characters at any point indicates the number of frogs needed. This is because each character in the sequence “croak” requires a frog, and the maximum count reflects the peak simultaneous croaking.
Frog Reusability: If all 5 characters reach a complete “croak” cycle, the frog responsible can be subtracted (indicating its availability for reuse), as each frog can croak multiple times but only once per complete “croak” sequence.

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        int n = croakOfFrogs.length();
        if (n % 5 != 0) {
            return -1;
        }
        int[] idx = new int[26];
        String s = "croak";
        for (int i = 0; i < 5; ++i) {
            idx[s.charAt(i) - 'a'] = i;
        }
        int[] cnt = new int[5];
        int ans = 0, x = 0;
        for (int k = 0; k < n; ++k) {
            int i = idx[croakOfFrogs.charAt(k) - 'a'];
            ++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;
    }
}

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        int n = croakOfFrogs.size();
        if (n % 5 != 0) {
            return -1;
        }
        int idx[26]{};
        string s = "croak";
        for (int i = 0; i < 5; ++i) {
            idx[s[i] - 'a'] = i;
        }
        int cnt[5]{};
        int ans = 0, x = 0;
        for (char& c : croakOfFrogs) {
            int i = idx[c - 'a'];
            ++cnt[i];
            if (i == 0) {
                ans = max(ans, ++x);
            } else {
                if (--cnt[i - 1] < 0) {
                    return -1;
                }
                if (i == 4) {
                    --x;
                }
            }
        }
        return x > 0 ? -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 {
	n := len(croakOfFrogs)
	if n%5 != 0 {
		return -1
	}
	idx := [26]int{}
	for i, c := range "croak" {
		idx[c-'a'] = i
	}
	cnt := [5]int{}
	ans, x := 0, 0
	for _, c := range croakOfFrogs {
		i := idx[c-'a']
		cnt[i]++
		if i == 0 {
			x++
			ans = max(ans, x)
		} else {
			cnt[i-1]--
			if cnt[i-1] < 0 {
				return -1
			}
			if i == 4 {
				x--
			}
		}
	}
	if x > 0 {
		return -1
	}
	return ans
}

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

1419. Minimum Number of Frogs Croaking

Description

Solutions

Strategy Overview

Key Points

All Problems

All Solutions

Welcome to Subscribe On Youtube

1419. Minimum Number of Frogs Croaking

Description

Solutions

Strategy Overview

Key Points

All Problems

All Solutions