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 = "free"
Output:"eefr"
Explanation:'e' appears twice while 'r' and 'f' both appear once. So 'e' must appear before both 'r' and 't'. Similarly, 'f' occurs earliest in string s, so 'f' comes before 'r'. "eerf" is not a valid output here. Hence, "eefr" is the output.

Example 2

Input: s = "Aabb"
Output:"bbAa"
Explanation: 'b' appears twice while 'A' and 'a' both appear once. Note that 'A' and 'a' are treated as different characters. "bbaA" is not a valid answer because 'A' occurs earlier than 'a' in s. Hence, "bbAa" is the output.