My solution to Facebook Hacker Cup 2013 Qualification Round: Beautiful Strings

beautifulstring.cpp

/*
The idea here is that to get the overall maximum beauty of the string you must assign
maximum beauty possible(26) to the most frequent alphabet and then 25 to the second most
frequent alphabet and so on.
And yes, in the code, sweetness and beauty means the same.
*/

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<climits>
#include<vector>
#include<iterator>
#include<set>

#define fr(i,a,b) for(int i=a; i<b; i++)
#define s(a) scanf("%d", &a)
#define p(a) printf("%d\n", a)
#define w(t) while(t--)
#define pb push_back
#define CLR(a) memset(a, 0, sizeof(a))

using namespace std;

typedef long long int lli;
typedef vector<int> VI;
typedef vector<string> VS;

int sweetness[26];
pair<char, int> frequency[26];

bool cmp(pair<char, int> p, pair<char, int> q) {
	return p.second < q.second;
}

int main() {
	int test;
	scanf("%d\n", &test);
	fr(t,1,test+1) {
		string s;
		getline(cin, s);
		string small;
		int len = s.length();
		CLR(frequency);
		CLR(sweetness);
        	// Initialize frequency[].first with a, b, c, ..., z.
		fr(i,0,26)
			frequency[i].first = 97+i;
		fr(i,0,len) {
			/* as the beauty for both uppercase and lowercase characters are same
        		   so lets first convert all characters to lowercase
        		*/
        		small[i] = tolower(s[i]);
        		/* Sorry punctuation marks, you're not beautiful 
        		   as only alphabets have got some beauty, so 
        		   we skip punctuations and spaces
        		*/
			if(small[i]==' '||ispunct(small[i]))
				continue;
			// and we increment the frequency of this particular alphabet
			frequency[small[i]-'a'].second++;
		}
        	// Sort the frequency[] according to frequency[].second
		sort(frequency, frequency+26, cmp);
		
        	// Assign max sweetness to the most frequent alphabet and so on...
        	for(int i=26; i>0; --i)
        		sweetness[frequency[i-1].first - 'a'] = i;
		int ans = 0;
		fr(i,0,len) {
			if(small[i] == ' ' || ispunct(small[i]))
               			continue;
			ans += sweetness[small[i]-'a'];
		}
		cout<<"Case #"<<t<<": "<<ans<<endl;
	}
	return 0;
}