Description
給定字串
text，回傳能用其中的字元拼出多少個 “balloon”。每個字元只能使用一次。
Example:
Input: text = “loonbalxballpoon” Output: 2
Intuition#
核心思路：統計
text中 b, a, l, o, n 各出現幾次，“balloon” 中 l 和 o 各需要 2 個，取最小值即為答案。
- “balloon” 需要：b:1, a:1, l:2, o:2, n:1
- 答案 = min(count_b, count_a, count_l/2, count_o/2, count_n)
Approaches#
1: 完整字元計數#
- 概念: 統計所有 26 個字母出現次數，再對 “balloon” 每個字母做除法取最小值
- 時間複雜度:
O(n)- 遍歷字串一次 - 空間複雜度:
O(1)- 固定大小陣列
class Solution {
fun maxNumberOfBalloons(text: String): Int {
val count = IntArray(26)
for (c in text) {
count[c - 'a']++
}
var result = count['b' - 'a']
result = minOf(result, count['a' - 'a'])
result = minOf(result, count['l' - 'a'] / 2)
result = minOf(result, count['o' - 'a'] / 2)
result = minOf(result, count['n' - 'a'])
return result
}
}⭐2: 對 “balloon” 字元計數取最小倍數#
- 概念: 同時統計
text和 “balloon” 的字元頻率，對每個必要字元計算可用倍數，取最小值 - 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun maxNumberOfBalloons(text: String): Int {
val countText = HashMap<Char, Int>()
for (c in text) {
countText[c] = (countText[c] ?: 0) + 1
}
val countBalloon = HashMap<Char, Int>()
for (c in "balloon") {
countBalloon[c] = (countBalloon[c] ?: 0) + 1
}
var result = Int.MAX_VALUE
for ((c, need) in countBalloon) {
result = minOf(result, (countText[c] ?: 0) / need)
}
return result
}
}🔑 Takeaways#
- Pattern: 字元頻率計數 + 瓶頸分析（取最小倍數）
- 關鍵技巧: 注意 “balloon” 中 l 和 o 出現兩次，需要除以 2；此模式適用於任何「用給定字元拼目標字串」的題目