Sort Characters By Frequency

MediumHeapbucket sort

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given a string s, rearrange its characters so that they are ordered by how often each one appears, from most frequent to least frequent. A character's **frequency** is the number of times it occurs in s. In the result, every occurrence of a given character must be grouped together (a run of identical characters), and runs of higher frequency must come before runs of lower frequency. Return the rearranged string. If two or more characters share the same frequency, they may appear in **any relative order** with respect to each other, so more than one valid answer may exist. Note that uppercase and lowercase letters are treated as distinct characters ('A' and 'a' count separately), and s may contain digits and other ASCII characters.

Examples

Input: s = "tree"
Output: "eetr"
`'e'` appears twice while `'t'` and `'r'` each appear once, so the two `'e'` characters come first. "eert" would also be accepted since `'t'` and `'r'` tie.
Input: s = "cccaaa"
Output: "cccaaa"
Both `'c'` and `'a'` appear three times, so each must form a contiguous run of three. "aaaccc" is equally valid.
Input: s = "Aabb"
Output: "bbAa"
`'b'` appears twice, so it comes first. `'A'` and `'a'` are different characters, each appearing once. "bbaA" is also valid.

Constraints

  • 1 <= s.length <= 5 * 10^5
  • `s` consists of uppercase and lowercase English letters and digits.
  • Any valid rearrangement (respecting frequency order) is accepted.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.