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;
  }
}
Report Error

Report ErrorClose

5 Responses to Facebook Hacker Cup – Beautiful Strings

  1. Aaron says:

    Actually the original question was,
    “You found the string that Johnny considered most beautiful. What is the maximum possible beauty of this string?”

    The example input is only an example. It’s not which of THOSE strings (in the example) is the most beautiful.

    The two clues are:
    1.) The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty.
    2.) Constraints: 5 ? m ? 50 / 2 ? length of s ? 500

    The answer is in those two clues. (Less than or equal to 500 characters in length and the highest beauty a letter can have is “26?)

    500 x 26 = 13,000
    So the maximum beauty a string can have is 13,000.

    Example input ABbCcc = 152 or a + 2b + 3c = 152 (in this example C = 26)
    So the most beautiful string possible would be five hundred “C”s or:
    cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
    cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
    cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
    cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
    cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc

  2. Jorge R says:

    Hola he estado leyendo en este tiempo tus post acerca de la hacker cup, va a participar en la de este año o ya participaste?, me ha sido de mucha utilidad leer tus post porque yo tambien uso java, aunque yo soy muy novato en esto, saludos

  3. Jorge R says:

    Gracias por contestar veo también que trabajaste en Oracle y estas trabajando en Google, sería bueno escuchar de tus experiencias en las entrevistas ¿que nivel de ejercicios te pusieron a resolver en esas entrevistas, supongo que como el dificil de la hackercup o algo más rudo?

    saludos

Leave a Reply

Your email address will not be published. Required fields are marked *


Please wrap source code in your comment with [code][/code] tags.
Set your Twitter account name in your settings to use the TwitterBar Section.