Sort Characters By Frequency LeetCode Solution

Last updated on October 5th, 2024 at 06:06 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

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
Scroll to Top