I could come up with only a solution using priority queue, which is `O(logN)`

. But after reading this solution made me realize there is more efficient solution.

For an example of `"tree"`

, first we iterate through the string and create a map whose key is each character, and a value is count. The result is `map[byte]int = {'t': 1, 'r': 1, 'e': 2}`

.

We also know that `2`

is the maximum count among all characters then. Let's call this `maxCount`

.

Next, create buckets `[][]byte`

from `0`

to `maxCount - 1`

(i.e. length = maxCount ).

Each bucket is `[]byte`

which can hold multiple characters as an array, and an index of bucket represents a count of each character.

The result is

```
[][]byte[0] = ['t', 'r'] // index 0 means count = 1
[][]byte[1] = ['e'] // index 1 means count = 2
```

Finally, we can iterate the buckets from last index to first, just append each character as many as `index + 1`

= count. The result is, `"eetr"`

.

```
func frequencySort(s string) string {
m := make(map[byte]int)
maxCount := 0
for i := 0; i < len(s); i++ {
if c, ok := m[s[i]]; !ok {
m[s[i]] = 1
} else {
m[s[i]] = c + 1
}
if m[s[i]] > maxCount {
maxCount = m[s[i]]
}
}
buckets := make([][]byte, maxCount)
for k, v := range m {
if len(buckets[v-1]) == 0 {
buckets[v-1] = []byte{k}
} else {
buckets[v-1] = append(buckets[v-1], k)
}
}
var b bytes.Buffer
for i := maxCount - 1; i >= 0; i-- {
for _, ch := range buckets[i] {
for j := 0; j < i+1; j++ {
b.WriteByte(ch)
}
}
}
return b.String()
}
```

The final loop is triple loops, but at most iteration can be ran only `N`

, length of the string. So `O(N)`

.