{"id":6649,"date":"2020-04-20T00:58:46","date_gmt":"2020-04-20T07:58:46","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6649"},"modified":"2020-04-20T01:19:39","modified_gmt":"2020-04-20T08:19:39","slug":"leetcode-1419-minimum-number-of-frogs-croaking","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1419-minimum-number-of-frogs-croaking\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1419. Minimum Number of Frogs Croaking"},"content":{"rendered":"\n

Given the string croakOfFrogs<\/code>, which represents a combination of the string “croak” from different frogs, that is, multiple frogs can croak at the same time, so multiple \u201ccroak\u201d are mixed. Return the minimum number of <\/em>different frogs to finish all the croak in the given string.<\/em><\/p>\n\n\n\n

A valid “croak” means a frog is printing 5 letters \u2018c\u2019, \u2019r\u2019, \u2019o\u2019, \u2019a\u2019, \u2019k\u2019 sequentially<\/strong>. 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.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> croakOfFrogs = \"croakcroak\"\nOutput:<\/strong> 1 \nExplanation:<\/strong> One frog yelling \"croak\"<\/strong> twice.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> croakOfFrogs = \"crcoakroak\"\nOutput:<\/strong> 2 \nExplanation:<\/strong> The minimum number of frogs is two. \nThe first frog could yell \"cr<\/strong>coak<\/strong>roak\".\nThe second frog could yell later \"crc<\/strong>oakroak<\/strong>\".\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> croakOfFrogs = \"croakcrook\"\nOutput:<\/strong> -1\nExplanation:<\/strong> The given string is an invalid combination of \"croak\"<\/strong> from different frogs.\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> croakOfFrogs = \"croakcroa\"\nOutput:<\/strong> -1\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= croakOfFrogs.length <= 10^5<\/code><\/li>
  • All characters in the string are: 'c'<\/code>, 'r'<\/code>, 'o'<\/code>, 'a'<\/code> or 'k'<\/code>.<\/li><\/ul>\n\n\n\n
    Solution: Hashtable<\/strong><\/h2>\n\n\n\n
    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.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minNumberOfFrogs(string croakOfFrogs) {\n    vector idx(26);\n    idx['c' - 'a'] = 0;\n    idx['r' - 'a'] = 1;\n    idx['o' - 'a'] = 2;\n    idx['a' - 'a'] = 3;\n    idx['k' - 'a'] = 4;\n    vector count(5);\n    int cur = 0;\n    int ans = 0;    \n    for (char ch : croakOfFrogs) {\n      const int i = idx[ch - 'a'];\n      ++count[i];\n      if (ch == 'c') {\n        ans = max(ans, ++cur);\n        continue;\n      }\n      if (count[i] > count[i - 1]) return -1;\n      if (ch == 'k') --cur;\n    }\n    return cur ? -1 : ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[82,177,180,4],"class_list":["post-6649","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-medium","tag-stack","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6649","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6649"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6649\/revisions"}],"predecessor-version":[{"id":6651,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6649\/revisions\/6651"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6649"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6649"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6649"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}