<p>Given a string <code>s</code>, sort it in <strong>decreasing order</strong> based on the <strong>frequency</strong> of the characters. The <strong>frequency</strong> of a character is the number of times it appears in the string.</p>

<p>Return <em>the sorted string</em>. If there are multiple answers, return <em>any of them</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;tree&quot;
<strong>Output:</strong> &quot;eert&quot;
<strong>Explanation:</strong> &#39;e&#39; appears twice while &#39;r&#39; and &#39;t&#39; both appear once.
So &#39;e&#39; must appear before both &#39;r&#39; and &#39;t&#39;. Therefore &quot;eetr&quot; is also a valid answer.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cccaaa&quot;
<strong>Output:</strong> &quot;aaaccc&quot;
<strong>Explanation:</strong> Both &#39;c&#39; and &#39;a&#39; appear three times, so both &quot;cccaaa&quot; and &quot;aaaccc&quot; are valid answers.
Note that &quot;cacaca&quot; is incorrect, as the same characters must be together.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;Aabb&quot;
<strong>Output:</strong> &quot;bbAa&quot;
<strong>Explanation:</strong> &quot;bbaA&quot; is also a valid answer, but &quot;Aabb&quot; is incorrect.
Note that &#39;A&#39; and &#39;a&#39; are treated as two different characters.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>5</sup></code></li>
	<li><code>s</code> consists of uppercase and lowercase English letters and digits.</li>
</ul>

class Solution {
public:
    string frequencySort(string s) {
        vector<pair<int , char>> hash('z' + 1 ,  {0,0});
        // for(int i = 0 ; i < s.size() ; i++){
        //     hash[s[i]] = {hash[s[i]].first +1 , (char)s[i]};
        // }
        // sort(hash.begin() ,hash.end());
        // // string ans ="";
        // // for(auto i : hash){
        // //     ans = string(i.first , i.second) + ans;   //it make temp string if size i.first having elements i.second
        // // }
        //         // TC and SC of both loop code is same O(L), O(L)
        // for(auto i : hash){
        //     int maxi = i.first;
        //     char c = i.second;
        //     string temp;
        //     while(maxi > 0){
        //         temp.push_back(c);
        //         maxi--;
        //     }
        //     ans = temp + ans;
        //     temp.clear();
            
        // }
        // return ans;



        // Memory Limit exceeds

        int maxi = INT_MIN;
        int arr[200] ={0};
        string ans ="";
        for(int i = 0 ; i < s.size() ; i++){
            arr[s[i]]++;
            maxi = max(maxi , arr[s[i]]);
        }
        while(maxi > 0){
            for(int i = 0 ; i < 200 ; i++){
                if(arr[i] == maxi){
                    int j = 0;
                    int count = maxi;

                    // string temp;
                    // while(j < count){
                    //     char el = i;
                    //     temp.push_back(el);
                    //     j++;
                    // }
                    // arr[i] = 0;
                    // ans = ans + temp;
                    // temp.clear();
                    ans = ans + string(maxi , i);
                }
            }
            maxi--;
        }
        return ans;
    }
};
13500