Character Frequency Sorting — Problem Statement & Solution Guide
Problem Description
Given a string s, find the frequency of each character and then reorder the string based on the frequency of characters in descending order. If two characters have the same frequency, the character with the smaller ASCII value will come first.
Examples
Input
tree
Output
eert
Explanation: Step-by-step: 1. Count the frequency of each character in the string 'tree': t(1), r(1), e(1). 2. Sort the characters based on their frequency in descending order and ASCII value in ascending order: e(1), r(1), t(1). 3. Reorder the string with the sorted characters: eert.
Input
hello
Output
ehllo
Explanation: Step-by-step: 1. Count the frequency of each character in the string 'hello': h(1), e(1), l(2), o(1). 2. Sort the characters based on their frequency in descending order and ASCII value in ascending order: l(2), e(1), h(1), o(1). 3. Reorder the string with the sorted characters: ehllo.
Constraints
- The length of the transmission message will not exceed 1000 characters.
- The transmission message will only contain lowercase English letters.
Optimal Approach & Strategy
The optimized approach can be achieved using the built-in functions of JavaScript. First, count the frequency of each character using an object. Then, use the Object.entries() method to get an array of key-value pairs, sort the array based on the frequency and ASCII value using the Array.sort() method, and finally use the array.reduce() method to reconstruct the sorted string.
Brute Force Approach
The brute-force approach is to sort the characters in the string based on their frequency and ASCII value, which can be achieved by iterating through the string, counting the frequency of each character using an object, sorting the keys of the object based on the frequency and ASCII value, and then reconstructing the sorted string. However, this approach has a time complexity of O(n^2) due to the sorting step.
Verified Code Solutions
class Solution {
public String characterFrequencySorting(String s) {
Map<Character, Integer> charFrequency = new HashMap<>();
for (char c : s.toCharArray()) {
charFrequency.put(c, charFrequency.getOrDefault(c, 0) + 1);
}
List<Character> sortedChars = new ArrayList<>();
for (char c : s.toCharArray()) {
sortedChars.add(c);
}
sortedChars.sort((a, b) -> -Integer.compare(charFrequency.get(a), charFrequency.get(b)));
sortedChars.sort(Comparator.comparingInt(c -> c));
return String.valueOf(sortedChars);
}
}def character_frequency_sorting(s: str) -> str:
char_frequency = {}
for char in s:
char_frequency[char] = char_frequency.get(char, 0) + 1
sorted_chars = sorted(s, key=lambda char: (-char_frequency[char], char))
return ''.join(sorted_chars)Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.