解題說明
Maximum Number of Balloons
題目描述:
給定一個字串 text,你需要用其中的字元拼出盡可能多的 "balloon" 單字。每個字元只能使用一次,回傳能拼出的最大數量。
解題思路:
"balloon" 由字元 b(1), a(1), l(2), o(2), n(1) 組成。我們只需統計 text 中這五個字元的出現次數,然後計算每個字元能貢獻幾個 "balloon":b、a、n 的次數直接使用,l 和 o 的次數需除以 2(因為一個 "balloon" 需要兩個 l 和兩個 o)。最終答案是所有貢獻數的最小值。
C++ 解法
複雜度分析
時間複雜度:O(n) — 遍歷字串一次統計字元頻率。
空間複雜度:O(1) — 只需大小為 26 的固定陣列。
虛擬碼
1. Initialize a frequency array of size 26 (all zeros)
2. For each character in text, increment its count
3. Compute the answer as the minimum of:
- count('b')
- count('a')
- count('l') / 2
- count('o') / 2
- count('n')
4. Return the answer其他解法
使用 HashMap:用 unordered_map 統計頻率,邏輯相同但常數較大。時間 O(n),空間 O(1)(最多 26 個鍵)。
通用化方法:將目標字串參數化,統計目標字串中各字元需求量,再用除法計算。適合目標不固定的情境,但本題中 "balloon" 是固定的,直接硬編碼更簡潔。
延伸思考
- 如果目標單字不是 "balloon" 而是任意字串,如何通用化解法?
- 若字元可重複使用(無限供應),這個問題會變成什麼?
- 如果要拼出多個不同單字且字元共用,如何最大化拼出的總單字數?