Given a string S, write a program to sort it in decreasing order based on the frequency of characters.

Problem Note

  • If two characters have the same frequency then whichever occurs earliest in S, comes first. In other words, the sorting must be stable.
  • Consider uppercase and lowercase different here i.e. 'A' and 'a' must be treated as two different characters.

Example 1

Input: S = "tree"
Output:"eetr"
Explanation:'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Similarly, 't' occurs earliest in S, so 't' comes before 'r'."eert" is not a valid answer.

Example 2

Input: S = "cccaaa"
Output:"cccaaa"
Explanation: Both 'c' and 'a' appear three times and c occurs earliest in S."aaaccc" is not a valid answer.
Note that "cacaca" is also incorrect, as the same characters must be together.

Example 3

Input: S = "Aabb"
Output:"bbAa"
Explanation:"bbaA" is not a valid answer because 'A' occurs earliest in S. Similarly 'A' and 'a' are treated as two different characters.