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 resvar 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
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;
}
}