451.sort-charaters-by-frequency.md

451. Sort Characters By Frequency

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

Heap

fun frequencySort(s: String): String {
    val counts = hashMapOf<Char, Int>()
    val maxHeap = PriorityQueue<Char>() { c1, c2 -> 
        counts[c2]!! - counts[c1]!!
    }
    for (c in s) {
        counts[c] = (counts[c] ?: 0) + 1
    }
    for (c in counts.keys) {
        maxHeap.add(c)
    }
    val results = StringBuilder()
    while (maxHeap.isNotEmpty()) {
        val c = maxHeap.poll()
        val frequency = counts[c]!!
        for (i in 0 until frequency) {
            results.append(c)
        }
    }
    return results.toString()
}

• Time Complexity: O(n + k lg k), n is the length of string, k is the number of unique character.
• Space Complexity: O(n + k) for hash table and heap.

Bucket Sort

fun frequencySort(s: String): String {
    val frequencyMap = hashMapOf<Char, Int>()
    for (c in s) {
        frequencyMap[c] = (frequencyMap[c] ?: 0) + 1
    }
    
    val buckets = List<MutableList<Char>>(s.length + 1) { _ -> mutableListOf<Char>() }
    frequencyMap.forEach { c, frequency ->
        for (i in 0 until frequency) {
            buckets[frequency].add(c)
        }
    }
    val results = StringBuilder()
    for (i in buckets.size - 1 downTo 0) {
        for (c in buckets[i]) {
            results.append(c.toString())
        }
    }
    return results.toString()
}

• Time Complexity: O(n + k).
• Space Complexity: O(n + k).