Sort Characters By Frequency

Problem Statement

Given a string s, you are required to rearrange the characters in the string such that they are sorted by the frequency of their appearances from highest to lowest. For example, in a string where the character 'a' appears more frequently than 'b', the sorted string should start with 'a'. If two characters have the same frequency, they can be placed in any order in the result as long as characters of the same type are grouped together. The solution should return any valid string that meets these criteria.

Examples

Example 1

Input:

s = "tree"

Output:

"eert"

Explanation:

'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2

Input:

s = "cccaaa"

Output:

"aaaccc"

Explanation:

Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3

Input:

s = "Aabb"

Output:

"bbAa"

Explanation:

"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

Constraints

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

Approach and Intuition

When addressing the problem of sorting characters by frequency, a clear and structured approach can be highly effective. Here’s how one might think about solving the problem:

1. Understand and parse the input:

   • The goal is to reorganize the characters of string s in a way that the characters that occur more frequently are positioned before those that occur less frequently.

2. Formulate a plan:

   • Count the frequency of each character in the string.
   • Use this frequency to sort the characters, with those having higher frequency coming first.
   • If frequencies are tied, any order is acceptable as long as the same characters are contiguous.

3. Implement the plan:

   • Use a hashmap or dictionary to associate each character with its frequency of occurrence in the string.
   • Convert the hashmap into a list of tuples, each containing a character and its frequency.
   • Sort this list based on the frequency, in descending order.
   • Construct the result string by repeating each character in the sorted list by its frequency.

4. Consider edge cases:

   • Single character strings: should return the character itself.
   • Strings where all characters have the same frequency can be returned in any order—the requirement only mandates grouping of like characters.

This method efficiently groups characters by frequency and should work within the constraints provided. Each character is processed in a straightforward manner, ensuring that even strings near the upper limit are handled appropriately. The provided examples demonstrate various scenarios including different characters with the same frequency and the handling of uppercase versus lowercase distinctions.

Solutions

public String sortCharactersByFrequency(String str) {
    if (str == null || str.isEmpty()) return str;
    
    Map<Character, Integer> frequencyMap = new HashMap<>();
    for (char ch : str.toCharArray()) {
        frequencyMap.put(ch, frequencyMap.getOrDefault(ch, 0) + 1);
    }
    
    int maxFreq = Collections.max(frequencyMap.values());
    
    List<List<Character>> buckets = new ArrayList<>();
    for (int i = 0; i <= maxFreq; i++) {
        buckets.add(new ArrayList<>());
    }
    for (Character key : frequencyMap.keySet()) {
        int frequency = frequencyMap.get(key);
        buckets.get(frequency).add(key);
    }
    
    StringBuilder result = new StringBuilder();
    for (int i = buckets.size() - 1; i >= 1; i--) {
        for (Character c : buckets.get(i)) {
            for (int j = 0; j < i; j++) {
                result.append(c);
            }
        }
    }
    return result.toString();
}