Golang O(N) solution using count buckets


  • 0

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


Log in to reply
 

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