Frequency-Based Character Ordering

MEDIUM15 pts

You are given a string s consisting of characters. Your task is to rearrange all characters in the string such that they are ordered by their occurrence frequency in descending order — characters that appear more frequently should come before characters that appear less frequently.

When constructing the output, all occurrences of the same character must be grouped together consecutively. For example, if a character appears 3 times, all 3 occurrences must appear adjacent to each other in the result.

If two or more characters share the same frequency, their relative order in the output can be arbitrary. This means multiple valid outputs may exist for a given input, and any valid arrangement satisfying the frequency ordering constraint is acceptable.

Important Notes:

The problem distinguishes between uppercase and lowercase letters — they are treated as distinct characters with independent frequency counts.
Digits (0-9) are also valid characters that should be processed using the same frequency-based rules.

Return the rearranged string with characters sorted by their frequency in descending order.

Example

Input

s = "tree"

Output

"eert" or "eetr"

Explanation

The character 'e' appears 2 times, while 'r' and 't' each appear only once. Since 'e' has the highest frequency, both 'e' characters must appear first in the output. The order of 'r' and 't' (both with frequency 1) can be arbitrary, making both "eert" and "eetr" valid solutions.

Example

Input

s = "cccaaa"

Output

"aaaccc" or "cccaaa"

Explanation

Both 'c' and 'a' appear exactly 3 times. Since they share the same frequency, either character can come first. However, all 3 'a's must be grouped together, and all 3 'c's must be grouped together. Note that "cacaca" would be invalid because the same characters are not grouped consecutively.

Example

Input

s = "Aabb"

Output

"bbAa" or "bbaA"

Explanation

The character 'b' appears 2 times, while 'A' and 'a' each appear once. Since uppercase and lowercase letters are treated as distinct characters, 'A' and 'a' are different. The 'b' characters come first (frequency 2), followed by 'A' and 'a' in any order (both have frequency 1).

Accepted0/0·0% Acceptance

Constraints

1 ≤ s.length ≤ 5 × 10⁵
s consists of uppercase English letters ('A' to 'Z'), lowercase English letters ('a' to 'z'), and digits ('0' to '9').

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

s =

"tree"

Frequency-Based Character Ordering

Hints

Frequency-Based Character Ordering

Hints