給定三個整數
a、b、c，分別代表字元 ‘a’、‘b’、‘c’ 的可用數量。構造一個最長的 “happy string”：不包含 “aaa”、“bbb”、“ccc” 作為子字串。回傳最長的 happy string（若有多個答案回傳任一）。
Example:
Input: a = 1, b = 1, c = 7 Output: “ccaccbcc”
Intuition
TIP
核心思路：貪心策略——每次優先用剩餘最多的字元，但若已連續出現兩次則改用次多的。
- 每次想用頻率最高的字元以最大化長度
- 但不能連續用三次同一字元
- 用 Max Heap 管理字元頻率，若堆頂字元已連續兩次，取第二個
Approaches
1. Greedy (3 chars, direct compare) — O(a + b + c) / O(1)
- Idea: 只有三種字元，不必用堆。每步在不造成連續三同的前提下，挑剩餘量最多的字元
- Time:
O(a + b + c)- 每步常數比較三個計數 - Space:
O(1)
class Solution {
fun longestDiverseString(a: Int, b: Int, c: Int): String {
val count = intArrayOf(a, b, c)
val sb = StringBuilder()
repeat(a + b + c) {
var best = -1
for (i in 0..2) {
if (count[i] == 0) continue
val ch = 'a' + i
val len = sb.length
if (len >= 2 && sb[len - 1] == ch && sb[len - 2] == ch) continue // 會連三
if (best == -1 || count[i] > count[best]) best = i
}
if (best == -1) return sb.toString()
sb.append('a' + best)
count[best]--
}
return sb.toString()
}
}⭐ 2. Max Heap + Greedy (generalizes to many chars) — O((a + b + c) * log 3) / O(1)
- Idea: Max Heap 依字元剩餘數量排序，每次取最多的字元放入結果；若與前兩個字元相同，改取次多的
- Time:
O((a + b + c) * log 3)=O(a + b + c) - Space:
O(1)
class Solution {
fun longestDiverseString(a: Int, b: Int, c: Int): String {
val maxHeap = PriorityQueue<IntArray>(compareByDescending { it[1] })
if (a > 0) maxHeap.offer(intArrayOf('a'.code, a))
if (b > 0) maxHeap.offer(intArrayOf('b'.code, b))
if (c > 0) maxHeap.offer(intArrayOf('c'.code, c))
val sb = StringBuilder()
while (maxHeap.isNotEmpty()) {
val first = maxHeap.poll()
val len = sb.length
// 檢查是否會連續三個相同
if (len >= 2 && sb[len - 1].code == first[0] && sb[len - 2].code == first[0]) {
// 改用次多的字元
if (maxHeap.isEmpty()) break
val second = maxHeap.poll()
sb.append(second[0].toChar())
second[1]--
if (second[1] > 0) maxHeap.offer(second)
maxHeap.offer(first) // 把 first 放回去
} else {
sb.append(first[0].toChar())
first[1]--
if (first[1] > 0) maxHeap.offer(first)
}
}
return sb.toString()
}
}🔑 Takeaways
- Pattern: 「最長不連續 k 次」問題 → Max Heap 貪心 + 連續次數檢查
- Key trick: 當最多的字元不能用時，用次多的字元「打斷」連續，再把最多的放回 heap；與 767. Reorganize String 類似但允許連續兩個