767. Reorganize String

Medium

Description

給定一個字串 s，重新排列字元使得相鄰兩個字元不同。若無法做到，回傳空字串。

Example:

Input: s = “aab” Output: “aba”

Intuition#

核心思路：每次貪心地取出現次數最多的字元放置，但要確保不與前一個字元相同。

若某個字元出現次數超過 (n + 1) / 2，則必定無解
每次取最多的字元放入結果，若與前一個相同，則改取第二多的
Max Heap 天然支持每次取頻率最高的字元

Approaches#

1: Sorting by Frequency#

概念: 按頻率排序後交錯放置，先填偶數位再填奇數位
時間複雜度: O(n)
空間複雜度: O(n)

class Solution {
    fun reorganizeString(s: String): String {
        val count = IntArray(26)
        for (c in s) count[c - 'a']++

        var maxCount = 0
        var maxChar = 0
        for (i in 0 until 26) {
            if (count[i] > maxCount) {
                maxCount = count[i]
                maxChar = i
            }
        }

        if (maxCount > (s.length + 1) / 2) return ""

        val result = CharArray(s.length)
        var idx = 0

        // 先放最多的字元在偶數位
        while (count[maxChar] > 0) {
            result[idx] = ('a' + maxChar)
            idx += 2
            count[maxChar]--
        }

        // 再放剩下的
        for (i in 0 until 26) {
            while (count[i] > 0) {
                if (idx >= s.length) idx = 1
                result[idx] = ('a' + i)
                idx += 2
                count[i]--
            }
        }

        return String(result)
    }
}

⭐2: Max Heap#

概念: 用 Max Heap 每次取頻率最高的兩個字元交替放置，確保相鄰不同
時間複雜度: O(n log 26) = O(n)
空間複雜度: O(26) = O(1)

class Solution {
    fun reorganizeString(s: String): String {
        val count = IntArray(26)
        for (c in s) count[c - 'a']++

        val maxHeap = PriorityQueue<IntArray>(compareByDescending { it[1] })
        for (i in 0 until 26) {
            if (count[i] > 0) {
                if (count[i] > (s.length + 1) / 2) return ""
                maxHeap.offer(intArrayOf(i, count[i]))
            }
        }

        val sb = StringBuilder()
        while (maxHeap.size >= 2) {
            val first = maxHeap.poll()
            val second = maxHeap.poll()

            sb.append(('a' + first[0]))
            sb.append(('a' + second[0]))

            first[1]--
            second[1]--

            if (first[1] > 0) maxHeap.offer(first)
            if (second[1] > 0) maxHeap.offer(second)
        }

        if (maxHeap.isNotEmpty()) {
            sb.append(('a' + maxHeap.poll()[0]))
        }

        return sb.toString()
    }
}

🔑 Takeaways#

Pattern: 「重排避免相鄰重複」→ Max Heap 每次取最多的兩個字元交替放置
關鍵技巧: 判斷無解條件：最大頻率 > (n+1)/2；每次取兩個字元可以保證不衝突。此 pattern 也適用於 621. Task Scheduler 和 1405. Longest Happy String