# Golang O(N) solution using count buckets

• 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)`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.