Practice/Microsoft/Leetcode 451. Sort Characters By Frequency

Leetcode 451. Sort Characters By Frequency

CodingMust

Problem

Given a string containing letters (both uppercase and lowercase) and digits, rearrange the characters so that they appear in descending order based on how frequently they occur in the string. Characters with higher frequency should come first, and all occurrences of the same character must be grouped together.

If multiple characters have the same frequency, they can appear in any order relative to each other.

Requirements

1. Return a string with characters arranged by decreasing frequency
2. All identical characters must be consecutive in the output
3. Treat uppercase and lowercase letters as distinct characters
4. When characters have equal frequency, any relative ordering between them is acceptable

Constraints

• 1 ≤ s.length ≤ 500,000
• s consists of uppercase and lowercase English letters and digits
• Time complexity should be O(n log n) or better
• Space complexity should be O(n) where n is the length of the string

Examples

Example 1:

Input: s = "tree" Output: "eert" Explanation: 'e' appears 2 times, 't' and 'r' each appear 1 time. One valid arrangement is "eert" (another would be "eetr").

Example 2:

Input: s = "cccaaa" Output: "aaaccc" Explanation: Both 'a' and 'c' appear 3 times each. Either "aaaccc" or "cccaaa" is acceptable.

Example 3:

Input: s = "Aabb" Output: "bbAa" Explanation: 'b' appears twice (highest frequency). 'A' and 'a' are different characters, each appearing once.