Description

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Example 1:

1Input: s = "tree"
2Output: "eert"
3Explanation: 'e' appears twice while 'r' and 't' both appear once.
4So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

1Input: s = "cccaaa"
2Output: "aaaccc"
3Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
4Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

1Input: s = "Aabb"
2Output: "bbAa"
3Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
4Note that 'A' and 'a' are treated as two different characters.

Constraints:

  • 1 <= s.length <= 5 * 10^5
  • s consists of uppercase and lowercase English letters and digits.

Solution

This problem is slightly complex than usual ones. In this case, we want to sort by character frequency which means first we need to find the frequency of each characters and store them in a map called frequencyMap. The next part is to sort this by frequency which means we have to convert frequency values to a List and sort them into descending order or rather sort the keys based on their values. In this we can use custom sort method which will sort by the values in frequencyMap.

Next part is to build the string from these characters based on their frequency. String is immutable which means we cannot perform operation like s = s + 'a'. It will work but it would end up consuming lots of extra memory and will require lot more operations. Instead of this, we could use StringBuffer or StringBuilder to build our string from the character list.

The difference between StringBuffer and StringBuilder is that StringBuffer is thread-safe option but can be little slower than StringBuilder.

 1class Solution {
 2    public String frequencySort(String s) {
 3        Map<Character, Integer> frequencyMap = new HashMap<>();
 4        for (char c : s.toCharArray()) {
 5            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
 6        }
 7
 8        Set<Character> keySet = frequencyMap.keySet();
 9        List<Character> charactersList = new ArrayList<>(keySet);
10        charactersList.sort((a, b) -> frequencyMap.get(b) - frequencyMap.get(a));
11
12        StringBuilder sb = new StringBuilder();
13        for (char c : charactersList) {
14            int count = frequencyMap.get(c);
15            while (count > 0) {
16                sb.append(c);
17                count--;
18            }
19        }
20        return sb.toString();
21    }
22}

To use StringBuffer, we can use similar code as shown in below snippet instead of creating instance of StringBuilder. Everything else remains same.

1StringBuffer sb = new StringBuffer();
  • Time Complexity: In this solution, creation of frequencyMap can take upto O(n). Next sorting of the List is of time complexity O(k log k) where k is the number of keys in frequencyMap. In worst case, if all characters are unique, it can be upto O(n log n). Next building the string using StringBuilder requires iterating through charactersList which can be of length k if there are k unique keys in frequencyMap. Again, this may take up to O(n) time. So, overall time complexity is O(n log n).
  • Space Complexity: Building HashMap is O(k) with k unique characters. Next, building string is O(n). So, overall space complexity is O(n).