Last updated on July 18th, 2024 at 10:43 pm

Here, We see Sort Characters By Frequency LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Hash Table, Heap

Companies

Amazon, Google

Level of Question

Medium

Sort Characters By Frequency LeetCode Solution

Problem Statement

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Example 1:
Input: s = “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: s = “cccaaa”
Output: “aaaccc”
Explanation: Both ‘c’ and ‘a’ appear three times, so both “cccaaa” and “aaaccc” are valid answers. Note that “cacaca” is incorrect, as the same characters must be together.

Example 3:
Input: s = “Aabb”
Output: “bbAa” E
xplanation: “bbaA” is also a valid answer, but “Aabb” is incorrect. Note that ‘A’ and ‘a’ are treated as two different characters.

1. Sort Characters By Frequency LeetCode Solution C++

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char,int> freq;
        priority_queue<pair<int,char>> maxheap;
        for(char c: s)
            freq[c]++;
        for(auto it: freq)
            maxheap.push({it.second,it.first});
        s="";   
        while(!maxheap.empty()){
            s+=string(maxheap.top().first,maxheap.top().second);
            maxheap.pop();
        }
        return s;        
    }
};

2. Sort Characters By Frequency LeetCode Solution Java

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> hm = new HashMap<>();
        for (char c : s.toCharArray()) {
            hm.put(c, hm.getOrDefault(c, 0) + 1);
        }
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
            (a, b) -> b.getValue() - a.getValue()
        );
        pq.addAll(hm.entrySet());
        StringBuilder result = new StringBuilder();
        while (!pq.isEmpty()) {
            Map.Entry<Character, Integer> entry = pq.poll();
            result.append(String.valueOf(entry.getKey()).repeat(entry.getValue()));
        }
        return result.toString();        
    }
}

3. Sort Characters By Frequency Solution JavaScript

var frequencySort = function(s) {
    const counter = new Map();
    for (const char of s) {
        counter.set(char, (counter.get(char) || 0) + 1);
    }
    const pq = Array.from(counter.entries());
    pq.sort((a, b) => b[1] - a[1]);
    let result = '';
    for (const [char, freq] of pq) {
        result += char.repeat(freq);
    }
    return result;
};

4. Sort Characters By Frequency Solution Python

class Solution(object):
    def frequencySort(self, s):
        counter = Counter(s)
        pq = [(-freq, char) for char, freq in counter.items()]
        heapq.heapify(pq)
        result = ''
        while pq:
            freq, char = heapq.heappop(pq)
            result += char * -freq
        return result