{"id":5545,"date":"2019-09-15T15:08:45","date_gmt":"2019-09-15T22:08:45","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5545"},"modified":"2019-09-15T15:11:42","modified_gmt":"2019-09-15T22:11:42","slug":"leetcode-1189-maximum-number-of-balloons","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1189-maximum-number-of-balloons\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1189. Maximum Number of Balloons"},"content":{"rendered":"\n<p>Given a string&nbsp;<code>text<\/code>, you want to use the characters of&nbsp;<code>text<\/code>&nbsp;to form as many instances of the word&nbsp;<strong>&#8220;balloon&#8221;<\/strong>&nbsp;as possible.<\/p>\n\n\n\n<p>You can use each character in&nbsp;<code>text<\/code>&nbsp;<strong>at most once<\/strong>. Return the maximum number of instances that can be formed.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/09\/05\/1536_ex1_upd.JPG\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> text = \"nlaebolko\"\n<strong>Output:<\/strong> 1\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/09\/05\/1536_ex2_upd.JPG\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> text = \"loonbalxballpoon\"\n<strong>Output:<\/strong> 2\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> text = \"leetcode\"\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= text.length &lt;= 10^4<\/code><\/li><li><code>text<\/code>&nbsp;consists of lower case English letters only.<\/li><\/ul>\n\n\n\n<p><strong>Solution: HashTable<\/strong><\/p>\n\n\n\n<p>Use a hashtable to count the occurrence of each letter and find the bottleneck one.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxNumberOfBalloons(string text) {\n    map<char, int> c;\n    for (char t : text) ++c[t];\n    return min({c['b'], c['a'], c['l'] \/ 2, c['o'] \/ 2, c['n']});\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a string&nbsp;text, you want to use the characters of&nbsp;text&nbsp;to form as many instances of the word&nbsp;&#8220;balloon&#8221;&nbsp;as possible. You can use each character in&nbsp;text&nbsp;at most&#8230;<\/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":[222,82,4],"class_list":["post-5545","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-easy","tag-hashtable","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5545","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=5545"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5545\/revisions"}],"predecessor-version":[{"id":5549,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5545\/revisions\/5549"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5545"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5545"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5545"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}