Sort Characters By Frequency

Solution For Sort Characters By Frequency

The problem Sort Characters By Frequency on LeetCode requires us to sort a given string in decreasing order of frequency of character occurrence. For example, for the input “tree”, we need to output “eert” (since ‘e’ appears twice, and ‘t’ and ‘r’ appear once each).

The most efficient way to solve this problem is to use a hash map to count the frequency of each character in the string. We can then sort the hash map by frequency and output the characters in the order of decreasing frequency.

Here is the step-by-step solution for the Sort Characters By Frequency problem on LeetCode:

Step 1: Create a hash map to count the frequency of each character in the given string.

HashMap<Character, Integer> charFreq = new HashMap<>();
for (char c : s.toCharArray()) {
charFreq.put(c, charFreq.getOrDefault(c, 0) + 1);
}

This code block creates a hash map called charFreq and loops through each character c in the string s. We use a getOrDefault method to increment the count for a character if it has already been seen before, or initialize it to zero if it’s a new character.

Step 2: Sort the hash map by value.

List<Character> chars = new ArrayList<>(charFreq.keySet());
Collections.sort(chars, (a, b) -> charFreq.get(b) - charFreq.get(a));

Here, we first create a list of all the characters in the hash map using the keySet method. We then sort the characters in the list using a Comparator that compares the frequency of the characters in the hash map.

Step 3: Build the final string by appending the characters in the order of decreasing frequency.

StringBuilder sb = new StringBuilder();
for (char c : chars) {
for (int i = 0; i < charFreq.get(c); i++) {
sb.append(c);
}
}
return sb.toString();

This code block uses a StringBuilder to append each character in the list chars in the order of decreasing frequency. We use the get method to get the frequency of each character in the original hash map and loop through it to append the character that many times. Finally, we return the string resulting from the StringBuilder.

Overall, this solution has a time complexity of O(n log n) (for the sorting step) and a space complexity of O(n) (for the hash map and the list of characters).

Step by Step Implementation For Sort Characters By Frequency

import java.util.*; 

class Solution { 

// Function to sort the characters by frequency 

static void sortByFreq(String str) 

{ 

// HashMap to store the frequencies 

Map hm = new HashMap<>(); 

for (int i = 0; i < str.length(); i++) { 

char ch = str.charAt(i); 

if (hm.containsKey(ch)) { 

int oldfreq = hm.get(ch); 

int newfreq = oldfreq + 1; 

hm.put(ch, newfreq); 

} 

else { 

hm.put(ch, 1); 

} 

} 

// Create a min heap 

PriorityQueue > pq = new PriorityQueue<>( 

new Comparator >() { 

public int compare(Map.Entry a,

Map.Entry b) 

{ 

return a.getValue() - b.getValue(); 

} 

}); 

// adding all elements of map into min heap 

for (Map.Entry entry : hm.entrySet()) { 

pq.add(entry); 

} 

// remove elements from min heap and print 

while (pq.size() != 0) { 

Map.Entry entry = pq.poll(); 

char ch = entry.getKey(); 

int freq = entry.getValue(); 

for (int i = 0; i < freq; i++) { 

System.out.print(ch); 

} 

} 

} 

// Driver code 

public static void main(String[] args) 

{ 

String str = "geeksforgeeks"; 

sortByFreq(str); 

} 

}
def frequencySort(s):
    # create a dictionary with characters as keys and frequencies as values
    freq = {}
    for char in s:
        if char in freq:
            freq[char] += 1
        else:
            freq[char] = 1
            
    # create a list of tuples (character, frequency) sorted by frequency in descending order
    freq_sorted = sorted(freq.items(), key=lambda x: x[1], reverse=True)
    
    # create and return a string consisting of the characters from the list of tuples
    res = ''
    for char, _ in freq_sorted:
        res += char * freq[char]
    return res
var frequencySort = function(s) {
    // create a map to store the characters and their frequencies
    let map = new Map();
    
    // iterate over the string, adding each character to the map
    for (let i = 0; i < s.length; i++) {
        let char = s.charAt(i);
        
        // if the character is already in the map, increment its frequency
        if (map.has(char)) {
            map.set(char, map.get(char) + 1);
        } else { // otherwise, set its frequency to 1
            map.set(char, 1);
        }
    }
    
    // sort the characters by frequency
    let sorted = [...map.entries()].sort((a, b) => {
        return b[1] - a[1];
    });
    
    // build and return the string
    let str = "";
    for (let i = 0; i < sorted.length; i++) {
        let char = sorted[i][0];
        let freq = sorted[i][1];
        
        for (let j = 0; j < freq; j++) {
            str += char;
        }
    }
    
    return str;
};
One possible solution is to use a map to keep track of the number of times each character appears in the string. Then, we can use a priority queue to sort the characters by their frequency. Finally, we can iterate through the priority queue and print out the characters in the order of their frequency.

#include  #include  #include  #include  #include  using namespace std; string sortCharactersByFrequency(string s) { map m; // map to keep track of character frequencies for (char c : s) { m[c]++; } // Use a priority queue to sort the characters by their frequency priority_queue, vector>, greater>> pq; for (auto it = m.begin(); it != m.end(); it++) { pq.push({it->second, it->first}); } // Iterate through the priority queue and print out the characters in order of their frequency string res = ""; while (!pq.empty()) { auto curr = pq.top(); pq.pop(); res += string(curr.first, curr.second); } return res; } int main() { string s = "tree"; cout << sortCharactersByFrequency(s) << endl; // eert return 0; }
using System; 
using System.Collections.Generic; 
using System.Linq; 

public class Solution { 

//This method sorts the characters in a string by their frequency in ascending order 
public string SortCharactersByFrequency(string s) { 

//Create a dictionary to store the characters and their frequencies 
Dictionary characterFrequency = new Dictionary(); 

//Loop through each character in the string and add it to the dictionary 
foreach(char c in s) { 

//If the character is already in the dictionary, increment its frequency 
if(characterFrequency.ContainsKey(c)) { 
characterFrequency[c]++; 
} 
//Otherwise, add the character to the dictionary with a frequency of 1 
else { 
characterFrequency[c] = 1; 
} 
} 

//Sort the dictionary by value in ascending order 
var sortedDictionary = characterFrequency.OrderBy(x => x.Value); 

//Initialize an empty string 
string sortedString = ""; 

//Loop through the sorted dictionary and add each character to the string 
foreach(var kvp in sortedDictionary) { 
for(int i = 0; i < kvp.Value; i++) { 
sortedString += kvp.Key; 
} 
} 

//Return the sorted string 
return sortedString; 
} 
}


Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]