Frequency Sort

Problem Statement:

Given a string s, sort its characters according to the following rules:

• Characters with a higher frequency (number of occurrences) appear before those with a lower frequency.
• If two characters have the same frequency, they should be arranged in alphabetical order (i.e. in lexicographical order).

In other words, for every character \(c\) in s, let \(f(c)\) denote its frequency. The output should be a string such that if \(f(c) > f(d)\), then c appears before d; if \(f(c) = f(d)\>, then c and d are sorted in ascending alphabetical order.

Examples:

• Input: tree → Output: eert
• Input: cccaaa → Output: aaaccc
• Input: Aabb → Output: bbAa

inputFormat

The input consists of a single line containing a string s. The string may contain both uppercase and lowercase letters.

outputFormat

Output the transformed string after sorting the characters by frequency (in descending order) and in alphabetical order for characters with equal frequency.

tree

eert