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 Maphm = 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
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 DictionarycharacterFrequency = 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; } }