Interview Bootcamp

0% completed

​

Solution: Sort Characters By Frequency (easy)

Problem Statement

Given a string, arrange its characters in descending order based on the frequency of each character. If two characters have the same frequency, their relative order in the output string can be arbitrary.

Example

  1. Input: s = "trersesess"
    • Expected Output: "sssseeerrt"
    • Justification: The character s appears four times, e three times, r two times and t only once. All characters are sorted based on their frequnecy.
  2. Input: s = "banana"
    • Expected Output: "aaannb".

.....

.....

.....

Like the course? Get enrolled and start learning!
Brandon W

Brandon W

· 2 years ago

I think difficulty for this problem needs reexamining, because on LeetCode this is marked as a Medium NOT an easy. Definitely made me feel better when I wasn't immediately getting it knowing it was harder than what it says.

Show 2 replies
senthil kumar

senthil kumar

· 2 years ago

public class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) 
            map.put(c, map.getOrDefault(c, 0) + 1);
                        
        List<Character> [] bucket = new List[s.length() + 1];
        for (char key : map.keySet()) {
            int frequency = map.get(key);
            if (bucket[frequency] == null) bucket[frequency] = new ArrayList<>();
            bucket[frequency].add(key);
        }
                
        StringBuilder sb = new StringBuilder();
        for (int pos = bucket.length - 1; pos >= 0; pos--)
            if (bucket[pos] != null)
                for (char c : bucket[pos])
                    for (int i = 0; i < pos; i++)
P P

P P

· 2 years ago

    StringBuilder result = new StringBuilder();
    PriorityQueue<Map.Entry<Character, Integer>> maxHeap =
            new PriorityQueue<>(((o1, o2) -> o2.getValue() - o1.getValue()));

    HashMap<Character, Integer> freqMap = new HashMap<>();

    for (char c : str.toCharArray()) {
        freqMap.merge(c, 1, Integer::sum);
    }

    maxHeap.addAll(freqMap.entrySet());

    while (!maxHeap.isEmpty()){
        Map.Entry<Character, Integer> entry = maxHeap.poll();
        String repeat = String.valueOf(entry.getKey()).repeat(entry.getValue());
        result.append(repeat);
    }

    // ToDo: Write Your Code Here.
    return result.toString();
}
V

vh1030478

· 2 years ago

The javascript use an array and sort base on the frequency instead of using a Heap.

This defeats the purpose of this challenge.

V

Viktor

· a month ago

I think that in the Bucket Sort approach, there is no need for maintaining the vector of vectors (or array of arrays). When constructing the resulting string, one just needs to append the character in question as many times as its bucket index tells.