Order Character Blocks by Their Frequencies

# Order Character Blocks by Their Frequencies Given a string `s`, rearrange all of its characters so that characters occurring more often come before characters occurring less often. Every occurrence of the same character must be together in one contiguous block. Return any valid rearranged string. Blocks with equal frequencies may appear in either order; there is no required alphabetical or other tie-break. Uppercase and lowercase letters are different characters. ### Interface `class Solution { public: string frequencySort(string s); };` ### Example 1 ```text Input: s = "bAAbb22" One valid output: "bbbAA22" ``` `b` occurs three times; `A` and `2` occur twice each. `"bbb22AA"` is another valid output. ### Example 2 ```text Input: s = "ZzZ77z" One valid output: "ZZzz77" ``` Each of `Z`, `z` and `7` occurs twice. `"77ZZzz"` also satisfies the requirements. The two letter cases remain distinct. ### Constraints - `1 <= s.length <= 500000`. - `s` contains only uppercase English letters, lowercase English letters and digits. ### What a Strong Answer Covers - Keeping every input character with its original multiplicity. - Keeping identical characters together and respecting decreasing block frequency. - Accepting different block orders when frequencies tie. - Time and space bounds at the maximum string length. ```hint What is fixed? Which properties of the output are fixed by the input, and which remain free when two characters occur equally often? ``` ### Follow-up Questions - If two implementations return different strings for the same input, how would you check that both satisfy the task without requiring equal-frequency blocks to appear in the same order?