Header Ad

HackerEarth Difficult Characters problem solution

In this HackerEarth Difficult Characters problem solution Yesterday, while Omar was trying to learn English, he saw that there are letters repeated many times in words while some other letters repeated only a few times or not repeated at all!

Of course, anyone can memorize the letters (repeated many times) better than the letters repeated few times, so Omar will concatenate all the words in the context he has, and try to know the difficulty of each letter according to the number of repetitions of each letter.

So Omar has now the whole context and wants to arrange the letters from the most difficult letter (repeated few times) to the less difficult letter (repeated many times).

If there are 2 letters with the same level of difficulty, the letter with a higher value of ASCII code will be more difficult.


HackerEarth Difficult Characters problem solution


HackerEarth Difficult Characters problem solution.

#include <bits/stdc++.h>

using namespace std;

int arr [26 + 1];
bool vis [26 + 1];

int main()
{
int n , t;
string s;

scanf("%d", &t);

while(t--){

memset(arr , 0 , sizeof arr);
memset(vis , false, sizeof vis);

cin >> s;

int len = s.size();

for(int i = 0; i < len; i++){

arr[ s[i] - 'a' ]++;
}

for(int i = 0; i < 26; i++){

int mini = 1e9;
char miniChar = '/';

for(int j = 25; j >= 0; j--){

if(arr[j] < mini && !vis[j]){

mini = arr[j];
miniChar = j + 'a';
}
}

vis[miniChar - 'a'] = true;

printf("%c ", miniChar);
}

printf("\n");
}

return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

#define bug() printf("BUG\n")
#define bug1(n) printf("bg1 %d\n",n)
#define bug2(a,b) printf("bg2 %d %d\n",a,b)
#define MOD 1000000007
#define ll long long
#define vi vector< int >
#define vll vector< long long >
#define vvi vector< vector< int > >
#define vvll vector< vector< long long > >
#define pi pair< int, int >
#define pll pair< long long, long long >
#define vpi vector< pair< int, int > >
#define vpll vector< pair< long long, long long > >
#define pb(n) push_back(n)
#define mp(a,b) make_pair(a,b)
#define printA(a,n) for(int i = 0;i < n;++i) cout<<a[i]<<" "; cout<<endl;

int main()
{
int t;
scanf("%d",&t);
assert(t >= 1 && t <= 10);
while(t--)
{
string s;
cin>>s;
vpi v;
for (int i = 0; i < 26; ++i)
{
v.pb(mp(0,i));
}
int len = s.length();
assert(len >= 1 && len <= 1000000);
for (int i = 0; i < len; ++i)
{
assert(s[i] >= 'a' && s[i] <= 'z');
v[s[i]-'a'].first += 1;
}
sort(v.begin(),v.end());
for (int i = 0,j; i < 26; ++i)
{
j = i+1;
int temp = i;
for (; j < 26; ++j,++i)
{
if(v[j].first != v[i].first)
break;
}
reverse(v.begin()+temp,v.begin()+j);
}
for (int i = 0; i < 26; ++i)
{
printf("%c ", v[i].second + 'a');
}
printf("\n");
}
return 0;
}

Post a Comment

0 Comments