Hirad Roshandel Hirad Roshandel - 20 days ago 12
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++)
{
if(map.containsKey(s.charAt(i)))
map.put(s.charAt(i),map.get(s.charAt(i))+1);
else
map.put(s.charAt(i),1);
}

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

@Override
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

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

StringBuilder builder = bew StringBuilder();
builder.append(e.getKey());

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

copyright

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

Comments