Hirad Roshandel Hirad Roshandel - 1 year ago 115
Java Question

Sort Characters By Frequency Java (Optimal Solution)

I'm trying to solve this question using Java. The goal is to sort a string in decreasing order based on the frequency of characters. For example "Aabb" is going to be "bbaA" or "bbAa". I have implemented a working solution but it's in O(n^2). I was wondering if someone out there has a better and more optimal solution.
Here is the code:

public class Solution
public String frequencySort(String s)
Map<Character,Integer> map =new HashMap<Character,Integer>();
for(int i=0;i<s.length();i++)

List<Map.Entry<Character,Integer>> sortedlist = new ArrayList<>(map.entrySet());
Collections.sort(sortedlist, new Comparator<Map.Entry<Character,Integer>>() {

public int compare(Map.Entry<Character, Integer> o1,
Map.Entry<Character, Integer> o2) {
return o2.getValue() - o1.getValue();

String lastString="";
for (Map.Entry<Character,Integer> e : sortedlist)
for(Integer j=0;j < e.getValue();j++)
lastString+= e.getKey().toString();
return lastString;

Answer Source

Your code doesn't pass because of string concatenation, use StringBuilder instead and I bet you will pass.

StringBuilder builder = bew StringBuilder();

return builder.toString();

There are a couple of other ideas how to sort elements by frequency.

  1. Use a sorting algorithm to sort the elements O(nlogn)
  2. Scan the sorted array and construct a 2D array of element and count O(n).
  3. Sort the 2D array according to count O(nlogn)

    Input 2 5 2 8 5 6 8 8

    After sorting we get 2 2 5 5 6 8 8 8

    Now construct the 2D array as

    2, 2

    5, 2

    6, 1

    8, 3

    Sort by count

    8, 3

    2, 2

    5, 2

    6, 1


Follow the link to take a look at other possible approaches.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download