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.
Try here before watching the video.
Approach 1
This problem can easily be solved using the Sorting technique. But in this article and video, we have explained the Priority Queue-based approach so that you have some clarity on how to use it in your problems.
Pseudocode for Approach 1
function frequencySort(s: string) -> string:
// Step 1: Create a map to store the frequency count of each character
frequencyCount = createEmptyMap()
// Step 2: Iterate through each character in the input string
for ch in s:
// Increment the count of the current character in the frequency map
frequencyCount[ch] += 1
// Step 3: Convert the keys of the frequency map to a list
characters = keys(frequencyCount)
// Step 4: Sort the characters based on their frequency count in descending order
sort(characters, compareFn(a, b) -> frequencyCount[b] - frequencyCount[a])
// Step 5: Initialize an empty string to store the sorted characters
sortedString = ""
// Step 6: Iterate through each character in the sorted list
for ch in characters:
// Get the frequency count of the current character
charCount = frequencyCount[ch]
// Append the current character to the sorted string 'charCount' times
repeat charCount times:
append ch to sortedString
// Step 7: Return the sorted string
return sortedString
Approach 2 - Priority Queue
💡
Don't have any idea about Heaps or Priority Queues? Check this video, you will understand what is it and how to use Heaps/Priority Queues in your problems.
Video Solution
Java Code
class Solution {
public String frequencySort(String s) {
Map<Character, Integer> frequencyMap = new HashMap<>();
for(char ch : s.toCharArray()) {
frequencyMap.put(ch, frequencyMap.getOrDefault(ch, 0) + 1);
}
PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());
for(Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
maxHeap.add(entry);
}
StringBuilder sortedString = new StringBuilder("");
while(!maxHeap.isEmpty()) {
Map.Entry<Character, Integer> entry = maxHeap.poll();
for(int i = 0; i < entry.getValue(); i++) {
sortedString.append(entry.getKey());
}
}
return sortedString.toString();
}
}
C++ Code
class Solution {
public:
struct comparator {
bool operator() (pair<char, int> &x, pair<char, int> &y) {
return y.second > x.second;
}
};
static string frequencySort(string s) {
unordered_map<char, int> frequencyMap;
for(char c : s) {
frequencyMap[c]++;
}
priority_queue<pair<char, int>, vector<pair<char, int>>, comparator> maxHeap;
for(const auto& entry : frequencyMap) {
maxHeap.push(entry);
}
string sortedString = "";
while(!maxHeap.empty()) {
auto entry = maxHeap.top();
maxHeap.pop();
for(int i = 0; i < entry.second; i++) {
sortedString += entry.first;
}
}
return sortedString;
}
};
Python Code
class Solution:
def frequencySort(self, s: str) -> str:
frequency_map = {}
for ch in s:
frequency_map[ch] = frequency_map.get(ch, 0) + 1
# while building max_heap in Python, we store values as negative.
# Watch this video if you don't know how to build max_heap in Python
# Link: https://www.youtube.com/watch?v=9IfRCVJ8H4E&list=PLw41HP7SUoAXmBjEPoJnG1_Wv8rDDiZbb&index=4
max_heap = [(-freq, ch) for ch, freq in frequency_map.items()]
heapq.heapify(max_heap)
sorted_string = ""
while max_heap:
freq, ch = heapq.heappop(max_heap)
sorted_string += ch * (-freq)
return sorted_string
Javascript Code
var frequencySort = function(s) {
const frequencyMap = {};
for (const ch of s) {
frequencyMap[ch] = (frequencyMap[ch] || 0) + 1;
}
const maxHeap = new MaxHeap();
for (const ch in frequencyMap) {
maxHeap.push({ ch, freq: frequencyMap[ch] });
}
maxHeap.heapify();
let sortedString = '';
while (maxHeap.length() > 0) {
const { ch, freq } = maxHeap.pop();
sortedString += ch.repeat(freq);
}
return sortedString;
};
class MaxHeap {
constructor() {
this.heap = [];
}
push(pair) {
this.heap.push(pair);
}
pop() {
const max = this.heap[0];
this.heap[0] = this.heap[this.heap.length - 1];
this.heap.pop();
this.heapifyDown();
return max;
}
heapify() {
for (let i = Math.floor(this.heap.length / 2); i >= 0; i--) {
this.heapifyDown(i);
}
}
heapifyDown(i = 0) {
while (true) {
let maxIndex = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < this.heap.length && this.heap[left].freq > this.heap[maxIndex].freq) {
maxIndex = left;
}
if (right < this.heap.length && this.heap[right].freq > this.heap[maxIndex].freq) {
maxIndex = right;
}
if (maxIndex !== i) {
[this.heap[i], this.heap[maxIndex]] = [this.heap[maxIndex], this.heap[i]];
i = maxIndex;
} else {
break;
}
}
}
length() {
return this.heap.length;
}
}
Go Code
type Pair struct {
Ch byte
Freq int
}
type MaxHeap []Pair
func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i].Freq > h[j].Freq }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) {
*h = append(*h, x.(Pair))
}
func (h *MaxHeap) Pop() interface{} {
old := *h
n := len(old)
item := old[n-1]
*h = old[0 : n-1]
return item
}
func frequencySort(s string) string {
frequencyMap := make(map[byte]int)
for i := 0; i < len(s); i++ {
frequencyMap[s[i]]++
}
maxHeap := &MaxHeap{}
for ch, freq := range frequencyMap {
*maxHeap = append(*maxHeap, Pair{ch, freq})
}
heap.Init(maxHeap)
sortedString := []byte{}
for maxHeap.Len() > 0 {
pair := heap.Pop(maxHeap).(Pair)
for i := 0; i < pair.Freq; i++ {
sortedString = append(sortedString, pair.Ch)
}
}
return string(sortedString)
}
Complexity Analysis
Time Complexity: O(N + K log K)
- Building a HashMap takes O(N) time.
- Assuming there are K unique characters, therefore building a priority queue will take O(K) time.
- And then again we are iterating over the K-size heap until it becomes empty and every time we delete one element from it, we iterate over the frequency of the deleted character, which will take O(N + K logK). Because deleting every time from the heap takes O(logK) to heapify itself.
- We can ignore K * logK as there are only 52 characters at max which is a constant number. But to be specific the time complexity is O(N + KlogK).
Space Complexity: O(K), we are using K size HashMap to store all unique characters.