Reorganize String ↗

• Idea: 按頻率排序後交錯放置，先填偶數位再填奇數位
• Time: O(n)
• Space: 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)
    }
}

• Idea: 用 Max Heap 每次取頻率最高的兩個字元交替放置，確保相鄰不同
• Time: O(n log 26) = O(n)
• Space: 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()
    }
}