1405. Longest Happy String

Medium
Description

給定三個整數 a、b、c，分別代表字元 ‘a’、‘b’、‘c’ 的可用數量。構造一個最長的 “happy string”：不包含 “aaa”、“bbb”、“ccc” 作為子字串。回傳最長的 happy string（若有多個答案回傳任一）。

Example:

Input: a = 1, b = 1, c = 7 Output: “ccaccbcc”

Intuition#

核心思路：貪心策略——每次優先用剩餘最多的字元，但若已連續出現兩次則改用次多的。

  • 每次想用頻率最高的字元以最大化長度
  • 但不能連續用三次同一字元
  • 用 Max Heap 管理字元頻率，若堆頂字元已連續兩次，取第二個

Approaches#

⭐1: Max Heap + Greedy#

  • 概念: Max Heap 依字元剩餘數量排序，每次取最多的字元放入結果；若與前兩個字元相同，改取次多的
  • 時間複雜度: O((a + b + c) * log 3) = O(a + b + c)
  • 空間複雜度: 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 貪心 + 連續次數檢查
  • 關鍵技巧: 當最多的字元不能用時，用次多的字元「打斷」連續，再把最多的放回 heap；與 767. Reorganize String 類似但允許連續兩個