Sort Characters By Frequency

Given a string s consisting only of lowercase English letters, rearrange its characters so that they are grouped in strictly decreasing order of frequency (the letter that occurs the most appears first). If two distinct letters have the same frequency, the letter that comes first alphabetically must appear before the other, so that the rearranged string is uniquely determined.

Input: A single line containing the string s. Output: Print a single line: the characters of s rearranged so they are grouped in strictly decreasing order of frequency, with ties broken by ascending alphabetical order.

1 <= |s| <= 8000 s consists only of lowercase English letters ('a'-'z')

Since the alphabet size (26) is tiny and fixed, this could ALSO be solved with a comparison sort at essentially no performance cost - the counting-sort framing here is more about demonstrating the technique than a strict necessity, unlike problems with much larger unbounded value ranges.

Rearrange a string's characters so the most frequent letter appears first, down to the least frequent, with alphabetical order breaking ties. Brute force: Count frequencies, then sort the distinct letters using a general comparison-based sort keyed by (frequency descending, then letter ascending) - this works and costs O(26 log 26), which is actually fine here since there are only 26 possible letters; a bucket-based counting approach is more of a stylistic/instructive choice for showcasing counting sort. Optimised: Since letter counts are bounded (0 to n) and there are only 26 possible letters, bucketing letters by their exact count value lets you process buckets from highest to lowest WITHOUT any general comparison sort at all - a direct application of counting sort's 'bucket by a bounded value' technique.

1. Count how many times each of the 26 letters occurs in the string. 2. Group letters by their FREQUENCY using counting sort (bucketing by count, since counts only range from 0 to n) instead of a general comparison sort. 3. Process buckets from the HIGHEST frequency down to the lowest; within a bucket (letters sharing the same frequency), emit them in ASCENDING alphabetical order to make the result uniquely determined.

Time: O(n + 26 log 26) - O(n) to count frequencies, plus a negligible sort of the alphabet-sized bucket structure. Space: O(1) - the frequency and bucket structures are always bounded by the 26-letter alphabet, regardless of the string's length.

All characters in s could be identical (output is just that repeated character), or every character could occur exactly once (output is s in alphabetical order).

Be ready to explain the alphabetical tie-breaking rule explicitly - it's what makes the output uniquely determined rather than just 'some valid ordering by frequency', a small but important detail this problem specifically requires.