# 451. Sort Characters By Frequency

Contents

Problem solution 451 “Sort Characters By Frequency” from LeetCode.

## Problem

Given a string, sort it in decreasing order based on the frequency of characters.

### example

 ``````1 2 3 4 5 6 7 8 9 `````` ``````Input: "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer. ``````
 ``````1 2 3 4 5 6 7 8 9 `````` ``````Input: "cccaaa" Output: "cccaaa" Explanation: Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer. Note that "cacaca" is incorrect, as the same characters must be together. ``````
 ``````1 2 3 4 5 6 7 8 9 `````` ``````Input: "Aabb" Output: "bbAa" Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters. ``````

## Solution

### Map + Bucket sort

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 `````` ``````func frequencySort(s string) string { a := make(map[byte]int, 0 ) maxc:=0 for idx:=range s { a[s[idx]]++ if a[s[idx]]>maxc { maxc = a[s[idx]] } } bucket := make([][]byte, maxc+1) for idx:=range a { if bucket[a[idx]] == nil { bucket[a[idx]] = make([]byte,0) } bucket[a[idx]] = append(bucket[a[idx]], idx) } res := "" for idx:=maxc;idx>=0;idx-- { if len(bucket[idx])!=0 { for kdx:=range bucket[idx] { for jdx:=0;jdx

### Priority queue

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 `````` ``````func frequencySort(s string) string { q := make(map[byte]int, 0) for idx:=range s { q[s[idx]]++ } pq := make(PQ, len(q)) i := 0 for value, priority := range q { pq[i] = &Item{ value: value, priority: priority, index: i, } i++ } heap.Init(&pq) res := "" for pq.Len() > 0 { item := heap.Pop(&pq).(*Item) for idx:=0;idx pq[j].priority } func (pq PQ) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] pq[i].index = i pq[j].index = j } func (pq *PQ) Push(x interface{}) { n := len(*pq) item := x.(*Item) item.index = n *pq = append(*pq, item) } func (pq *PQ) Pop() interface{} { old := *pq n := len(old) item := old[n-1] old[n-1] = nil item.index = -1 *pq = old[0 : n-1] return item } ``````