JANUARY 28, 2013
“Beautiful Strings” is the first and simplest of the 2013 Facebook Hacker Cup’s qualification round problems. It is valued at 20 of the 100 possible points for the round and is relatively straightforward.
The problem basically boils down to having to maximize the value a string can be given since each letter of the alphabet can be assigned a unique “beauty value”. The value assigned for each letter is different for each test case. The problem description is as follows:
Beautiful strings
When John was a little kid he didn't have much to do. There was no internet, no Facebook, and no programs to hack on. So he did the only thing he could... he evaluated the beauty of strings in a quest to discover the most beautiful string in the world.
Given a string s, little Johnny defined the beauty of the string as the sum of the beauty of the letters in it.
The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty. Johnny doesn't care about whether letters are uppercase or lowercase, so that doesn't affect the beauty of a letter. (Uppercase 'F' is exactly as beautiful as lowercase 'f', for example.)
You're a student writing a report on the youth of this famous hacker. You found the string that Johnny considered most beautiful. What is the maximum possible beauty of this string?
Input
The input file consists of a single integer m followed by m lines.
Output
Your output should consist of, for each test case, a line containing the string "Case #x: y" where x is the case number (with 1 being the first case in the input file, 2 being the second, etc.) and y is the maximum beauty for that test case.
Constraints
5 <= m <= 50 2 <= length of s <= 500 Example input
5
ABbCcc
Good luck in the Facebook Hacker Cup this year!
Ignore punctuation, please :)
Sometimes test cases are hard to make up.
So I just go consult Professor Dalves
Example output
Case #1: 152
Case #2: 754
Case #3: 491
Case #4: 729
Case #5: 646
Those of you who know how to code have probably figured out that this is a trivial problem. What needs to be done is count the number of occurrences for each letter and basically assign higher values to the letters that occur most frequently.
A simple way to do this is to have a counter for each letter, sort them and the go through the counters assigning values from 26 to 1 to the most through least frequent letters. Capitalization is not important so everything can be transformed to lower case and punctuation is ignored.
In other words, a string such as “This is a Test String, Cool!” could be converted to “thisisateststringcool” and then the occurrence frequency for each character can be counted. For this case we’d end up with something like this:
t:4
s:4
i:3
o:2
h:1
a:1
r:1
n:1
g:1
c:1
l:1
e:1
Afterwards we can assign the highest values to the letters that appeared more frequently and end up with something like (4*26 + 4*25 + 3*24 + 2*23 + 1*22 + 1*21 + 1*20 + 1*19 + 1*18 + 1*17 + 1*16 + 1*15) = 470 which would be the beauty value for this particular case.
This is what I’ve done in my implementation, which follows:
import java.util.Arrays;
import java.util.Scanner;
/**
* Solution for Facebook Hacker Cup 2013, qualification round problem
* "Beautiful Strings"
* https://www.facebook.com/hackercup/problems.php?pid=475986555798659
* &round=185564241586420
* @author Luis E. Argote Bolio luis@argote.mx
*/
public class BeautifulStrings {
private static Scanner in = new Scanner(System.in);
/**
* Main class reads the input, calls execution and prints output.
* @param args
*/
public static void main(String[] args) {
int totalCases = Integer.parseInt(in.nextLine());
for (int caseNo = 1; caseNo <= totalCases; caseNo++) {
System.out.println("Case #" + caseNo + ": " + execute(in.nextLine()));
}
}
/**
* Does the actual work for each test case.
* @param caseInput The string for which to get the maximum beauty value.
* @return The maximum beauty value of the string.
*/
public static int execute(String caseInput) {
// Since upper case and lower case are equal, convert to lower case.
char[] chars = caseInput.toLowerCase().toCharArray();
// Initialize occurrence count for all chars at 0.
int[] possibleChars = new int[26];
Arrays.fill(possibleChars, 0);
// Check the frequency for the valid characters.
for (char c : chars) {
// Ignore invalid characters.
if (c < 'a' || c > 'z') {
continue;
}
possibleChars[c - 'a']++;
}
Arrays.sort(possibleChars);
int total = 0;
// Value the most frequently appearing characters highest.
for (int i = 0; i < 26; i++) {
total += possibleChars[25 - i] * (26 - i);
}
return total;
}
}