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

Java

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;
        }
    }
}

Java

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        int length = croakOfFrogs.length();
        if (length % 5 != 0)
            return -1;
        Map<Character, Integer> letterIndexMap = new HashMap<Character, Integer>();
        String croak = "croak";
        for (int i = 0; i < 5; i++)
            letterIndexMap.put(croak.charAt(i), i);
        int curSize = 0;
        int maxSize = 0;
        int[] counts = new int[5];
        for (int i = 0; i < length; i++) {
            char c = croakOfFrogs.charAt(i);
            int index = letterIndexMap.get(c);
            if (index == 0) {
                counts[index]++;
                curSize++;
                maxSize = Math.max(maxSize, curSize);
            } else {
                counts[index - 1]--;
                if (counts[index - 1] < 0)
                    return -1;
                if (index < 4)
                    counts[index]++;
                else
                    curSize--;
            }
        }
        for (int i = 0; i < 5; i++) {
            if (counts[i] != 0)
                return -1;
        }
        return maxSize;
    }
}

All Problems

All Solutions