題目描述:
給定一個字串 text,你需要用其中的字元拼出盡可能多的 "balloon" 單字。每個字元只能使用一次,回傳能拼出的最大數量。
解題思路:
"balloon" 由字元 b(1), a(1), l(2), o(2), n(1) 組成。我們只需統計 text 中這五個字元的出現次數,然後計算每個字元能貢獻幾個 "balloon":b、a、n 的次數直接使用,l 和 o 的次數需除以 2(因為一個 "balloon" 需要兩個 l 和兩個 o)。最終答案是所有貢獻數的最小值。
時間複雜度: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" 是固定的,直接硬編碼更簡潔。