Problem

Given a string, sort it in descending order based on the frequency of characters. If two characters have same frequency, their order in the output string does not matter. However, characters with same value should be together in the output.

Let's go through few examples to understand the problems:

Example 1

Input:

"tree"

Output:

"eert"

'e' appears twice while 'r' and 't' both appear once. Hence, 'e' must appear before both 'r' and 't'. Output "eetr" is also valid as 'r' and 't' have same frequency. Please note that the order of 'r' and 't' does not matter.

Example 2

Input:

"cccaaa"

Output:

"cccaaa"

Both 'c' and 'a' appear three times. Hence, "aaaccc" is also a valid answer.

Example 3

Input:

"Aabb"

Output:

"bbAa"

'b' appears twice, 'A' and 'a' both appear once. Please note that lower case and upper case characters are treated as different characters.

Algorithm and Data Structure

We can solve this problem by using a hashtable or dictionary to count the frequency of each character and a bucket sort to sort the characters based on frequency. Bucket sort sorts an array of values by distributing the elements of an input array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.

Solution

Here is a Python solution using a dictionary and a bucket sort to solve this problem:

1
2Python
3class Solution:
4  def frequencySort(self, s: str) -> str:
5    # frequency counter
6    count = collections.Counter(s)
7    # bucket for all frequencies
8    bucket = [[] for _ in range(len(s) + 1)]
9    # output string
10    res = []
11    # sorting frequencies
12    for k, v in count.items():
13      bucket[v].append(k * v)
14    # assembling string in reversed order
15    for i in range(len(s), -1, -1):
16      for j in bucket[i]:
17        res.append(j)
18    return "".join(res)

This Python solution first uses a collections.Counter to count the frequency of each character in the string. Then it uses a bucket sort to sort the characters by frequency. The output string is assembled in reversed order of frequency.This similar problem can also be approached in different languages such as JavaScript and Java. The basic algorithm remains the same i.e., calculating the frequency of every character in the string, sorting them in descending order of their frequencies and finally assembling them back to create a new sorted string.

Below is how this problem can be implemented in JavaScript and Java:

JavaScript Solution

1
2JavaScript
3var frequencySort = function(s) {
4    const count = new Map();
5    for(const ch of s){
6        if(count.has(ch)){
7            count.set(ch, count.get(ch) + 1);
8        }else{
9            count.set(ch, 1);
10        }   
11    }
12    const sorted = Array.from(count.entries()).sort((a,b)=>b[1] - a[1]());
13    let result = '';
14    for(const [ch, freq] of sorted){
15        result += ch.repeat(freq);
16    }
17    return result;
18};

This JavaScript solution uses a map to count the frequency of each character in the string, sorts the characters by frequency using the sort method, and creates the output string by repeating each character by its frequency.

Java Solution

1
2Java
3class Solution {
4    public String frequencySort(String s) {
5        if(s == null || s.length() == 0) return s;
6        Map<Character, Integer> map = new HashMap<>();
7        for(char c: s.toCharArray())
8            map.put(c, map.getOrDefault(c, 0) + 1);
9      
10        PriorityQueue<Character> heap = new PriorityQueue<>((a, b) -> Integer.compare(map.get(b), map.get(a)));
11        heap.addAll(map.keySet());
12      
13        StringBuilder sb = new StringBuilder();
14        while(!heap.isEmpty()) {
15            char c = heap.poll();
16            for(int i = 0; i < map.get(c); i++)
17                sb.append(c);
18        }
19      
20        return sb.toString();
21    }
22}

This Java solution uses a HashMap to count the frequency of each character in the string, and a PriorityQueue (which is implemented as a heap) to sort the characters by frequency. The PriorityQueue sorts the characters in descending order of frequency. The output string is assembled by appending each character by its frequency.