Problem Description
Explanation
To solve this problem, we can use a hashmap to keep track of the count of each letter ('c', 'r', 'o', 'a', 'k') encountered in the given string. We iterate through the string and maintain the count of each letter as we encounter it. At any point, if the count of a letter is less than the count of the previous letter encountered, we return -1 as the string is not a valid combination.
We also keep track of the maximum number of frogs needed by checking the count of 'c' and 'k'. At the end, if all counts are equal, we return the maximum count of 'c' or 'k' as the minimum number of frogs needed. Otherwise, we return -1.
- Time complexity: O(n) where n is the length of the input string.
- Space complexity: O(1) because the hashmap has a fixed size of 5 for the 5 different letters.
Solutions
class Solution {
public int minNumberOfFrogs(String croakOfFrogs) {
int[] count = new int[5]; // c, r, o, a, k
int frogs = 0;
int maxFrogs = 0;
for (char c : croakOfFrogs.toCharArray()) {
if (c == 'c') {
count[0]++;
maxFrogs = Math.max(maxFrogs, count[0]);
} else if (c == 'r') {
count[1]++;
if (count[1] > count[0]) return -1;
} else if (c == 'o') {
count[2]++;
if (count[2] > count[1]) return -1;
} else if (c == 'a') {
count[3]++;
if (count[3] > count[2]) return -1;
} else if (c == 'k') {
count[4]++;
if (count[4] > count[3]) return -1;
frogs = Math.max(frogs, count[4]);
} else {
return -1;
}
}
if (count[0] == count[1] && count[1] == count[2] && count[2] == count[3] && count[3] == count[4]) {
return maxFrogs;
} else {
return -1;
}
}
}Loading editor...