Sorted String

Little Ashish got a lot of strings as his birthday gift. He does not mind getting so many strings for free; in fact, he loves them. But, on noticing all the strings he received as a gift, Little Ashish, who's also a snob and a bit OCD kind of a guy, realizes that he does not like the way in which the strings are arranged.

He likes his strings sorted, in a different kind of way. He wants his strings to be sorted based on the count of characters present in the string. For instance, if the string is: "aaabbc", then the desired string would be cbbaaa. In the case where the count of two characters is the same, then the lexicographically smaller one will be printed first. For instance: "aabbcc" then, the output will be: "aabbcc".

Example:

Input:  s = "aabbccdd"
Output: aabbccdd

Approach

C++

#include <bits/stdc++.h>
using namespace std;

string sortedString(string s)
{
    string res = "";

    int f[26] = {0};
    for (int i = 0i < s.size(); i++)
        f[s[i] - 'a']++;
    int pmin1 = INT_MAX;
    while (res.size() != s.size())
    {
        min1 = INT_MAX;
        for (int j = 0j < 26j++)
        {
            if (f[j] && f[j] < min1)
            {
                min1 = f[j];
                p = j;
            }
        }
        while (min1--)
        {
            res += p + 97;
        }
        f[p] = 0;
    }
    return res;
}
int main()
{
    string s = "aabbccdd";

    cout << sortedString(s<< "\n";

    return 0;
}


No comments:

Post a Comment