451. Sort Characters By Frequency

Intuition

We need to reorder the characters in a string so that the characters with higher frequencies appear first. This is a classic case where we want to count frequencies, and then sort or prioritize based on those frequencies.

Complexity

Space Complexity	Time Complexity
$\text{O}(N)$	$\text{O}(N*\log{N})$

Code

public String frequencySort(String inputString) {
    // Frequency array for all ASCII characters
    int[] charFrequency = new int[256];

    // Count frequency of each character
    for (int i = 0; i < inputString.length(); ++i) {
        charFrequency[inputString.charAt(i)]++;
    }

    // Max-heap to sort characters by frequency in descending order
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
        (a, b) -> Integer.compare(b[1], a[1])
    );

    // Populate heap with characters that have a non-zero frequency
    for (int i = 0; i < 256; ++i) {
        if (charFrequency[i] > 0) {
            maxHeap.add(new int[]{i, charFrequency[i]});
        }
    }

    StringBuilder result = new StringBuilder();

    // Build the final string using the sorted characters
    while (!maxHeap.isEmpty()) {
        int[] entry = maxHeap.remove();
        char character = (char) entry[0];
        int frequency = entry[1];

        // Append the character `frequency` number of times
        while (frequency-- > 0) {
            result.append(character);
        }
    }

    return result.toString();
}