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'
.
Solution: Hashtable
Count the frequency of the letters, we need to make sure f[c] >= f[r] >= f[o] >= f[a] >= f[k] holds all the time, otherwise return -1.
whenever encounter c, increase the current frog, whenever there is k, decrease the frog count.
Don’t forget to check the current frog number, should be 0 in the end, otherwise there are open letters.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua class Solution { public: int minNumberOfFrogs(string croakOfFrogs) { vector<int> idx(26); idx['c' - 'a'] = 0; idx['r' - 'a'] = 1; idx['o' - 'a'] = 2; idx['a' - 'a'] = 3; idx['k' - 'a'] = 4; vector<int> count(5); int cur = 0; int ans = 0; for (char ch : croakOfFrogs) { const int i = idx[ch - 'a']; ++count[i]; if (ch == 'c') { ans = max(ans, ++cur); continue; } if (count[i] > count[i - 1]) return -1; if (ch == 'k') --cur; } return cur ? -1 : ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment