Formatted question description: https://leetcode.ca/all/451.html

451. Sort Characters By Frequency (Medium)

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

Example 1:

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.

Example 2:

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.

Example 3:

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.

Related Topics:
Hash Table, Heap

Similar Questions:

Solution 1.

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        char[] array = s.toCharArray();
        for (char c : array) {
            int count = map.getOrDefault(c, 0);
            count++;
            map.put(c, count);
        }
        List<CharacterCount> list = new ArrayList<CharacterCount>();
        Set<Character> keySet = map.keySet();
        for (char c : keySet) {
            int count = map.getOrDefault(c, 0);
            list.add(new CharacterCount(c, count));
        }
        Collections.sort(list);
        StringBuffer sortedSB = new StringBuffer();
        for (CharacterCount characterCount : list) {
            char character = characterCount.character;
            int count = characterCount.count;
            for (int i = 0; i < count; i++)
                sortedSB.append(character);
        }
        return sortedSB.toString();
    }
}

class CharacterCount implements Comparable<CharacterCount> {
    char character;
    int count;

    public CharacterCount(char character, int count) {
        this.character = character;
        this.count = count;
    }

    public int compareTo(CharacterCount characterCount2) {
        return characterCount2.count - this.count;
    }
}

############

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> counter = new HashMap<>();
        for (char c : s.toCharArray()) {
            counter.put(c, counter.getOrDefault(c, 0) + 1);
        }
        List<Character>[] buckets = new List[s.length() + 1];
        for (Map.Entry<Character, Integer> entry : counter.entrySet()) {
            char c = entry.getKey();
            int freq = entry.getValue();
            if (buckets[freq] == null) {
                buckets[freq] = new ArrayList<>();
            }
            buckets[freq].add(c);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = s.length(); i >= 0; --i) {
            if (buckets[i] != null) {
                for (char c : buckets[i]) {
                    for (int j = 0; j < i; ++j) {
                        sb.append(c);
                    }
                }
            }
        }
        return sb.toString();
    }
}

// OJ: https://leetcode.com/problems/sort-characters-by-frequency/
// Time: O(NlogN)
// Space: O(C)
class Solution {
public:
    string frequencySort(string s) {
        int cnt[256] = {};
        for (char c : s) cnt[c]++;
        sort(s.begin(), s.end(), [&](char a, char b) {
            return cnt[a] == cnt[b] ? a > b : cnt[a] > cnt[b];
        });
        return s;
    }
};

class Solution:
    def frequencySort(self, s: str) -> str:
        counter = Counter(s)
        buckets = defaultdict(list)
        for c, freq in counter.items():
            buckets[freq].append(c)
        res = []
        for i in range(len(s), -1, -1):
            if buckets[i]:
                for c in buckets[i]:
                    res.append(c * i)
        return ''.join(res)

############

from collections import Counter


class Solution(object):
  def frequencySort(self, s):
    """
    :type s: str
    :rtype: str
    """
    d = Counter(s)
    buf = {}
    for k, v in d.items():
      buf[v] = buf.get(v, "") + k * v
    ans = ""
    for i in reversed(range(0, len(s))):
      ans += buf.get(i, "")
    return ans

type pair struct {
	b   byte
	cnt int
}

func frequencySort(s string) string {
	freq := make(map[byte]int)
	for _, r := range s {
		freq[byte(r)]++
	}
	a := make([]pair, 0)
	for k, v := range freq {
		a = append(a, pair{b: k, cnt: v})
	}
	sort.Slice(a, func(i, j int) bool { return a[i].cnt > a[j].cnt })
	var sb strings.Builder
	for _, p := range a {
		sb.Write(bytes.Repeat([]byte{p.b}, p.cnt))
	}
	return sb.String()
}

function frequencySort(s: string): string {
    const map = new Map<string, number>();
    for (const c of s) {
        map.set(c, (map.get(c) ?? 0) + 1);
    }
    return [...map.entries()]
        .sort((a, b) => b[1] - a[1])
        .map(([k, v]) => k.padStart(v, k))
        .join('');
}

use std::collections::HashMap;
impl Solution {
    pub fn frequency_sort(s: String) -> String {
        let mut map = HashMap::new();
        for c in s.chars() {
            map.insert(c, map.get(&c).unwrap_or(&0) + 1);
        }
        let mut arr = map.into_iter().collect::<Vec<(char, i32)>>();
        arr.sort_unstable_by(|(_, a), (_, b)| b.cmp(&a));
        arr.into_iter()
            .map(|(c, v)| vec![c; v as usize].into_iter().collect::<String>())
            .collect()
    }
}

 class Solution {
    /**
     * @param String $s
     * @return String
     */
    function frequencySort($s) {
        for ($i = 0; $i < strlen($s); $i++) {
            $hashtable[$s[$i]] += 1;
        }
        arsort($hashtable);
        $keys = array_keys($hashtable);
        for ($j = 0; $j < count($keys); $j++) {
            $rs = $rs.str_repeat($keys[$j], $hashtable[$keys[$j]]);
        }
        return $rs;
    }
};

451 - Sort Characters By Frequency

451. Sort Characters By Frequency (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

451. Sort Characters By Frequency (Medium)

Solution 1.

All Problems

All Solutions