Last updated on February 4th, 2025 at 02:08 am

Here, we see a Sort Characters By Frequency LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Hash Table, Heap

Companies

Amazon, Google

Level of Question

Medium

Sort Characters By Frequency LeetCode Solution

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

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Top ‘K’ Elements”. This pattern is commonly used when we need to process elements based on their frequency or priority, often utilizing data structures like heaps (priority queues) or sorting mechanisms. In this case, the code sorts characters in a string based on their frequency in descending order.

3. Code Implementation in Different Languages

3.1 Sort Characters By Frequency 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;        
    }
};

3.2 Sort Characters By Frequency 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.3 Sort Characters By Frequency 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;
};

3.4 Sort Characters By Frequency 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

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n + k log k)	O(n + k)
Java	O(n + k log k)	O(n + k)
JavaScript	O(n + k log k)	O(n + k)
Python	O(n + k log k)	O(n + k)