type pairs [][]int

func (ps pairs) Len() int           { return len(ps) }
func (ps pairs) Less(i, j int) bool { return ps[j][0] < ps[i][0] }
func (ps pairs) Swap(i, j int)      { ps[i], ps[j] = ps[j], ps[i] }

func frequencySort(s string) string {
	freq := make([]int, 256)
	for _, r := range s {
		freq[r]++
	}
	var ps pairs = make([][]int, 0)
	for i := 0; i < 256; i++ {
		ps = append(ps, []int{freq[i], i})
	}
	sort.Sort(ps)
	n := len(s)
	res := make([]rune, n)
	for i, j := 0, 0; i < n; i++ {
		for ps[j][0] == 0 {
			j++
		}
		res[i] = rune(ps[j][1])
		ps[j][0]--
	}
	return string(res)
}