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++)
{
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 Source

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.

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