The Beauty and the Strings

This originally appeared in Facebook's hacker cup 2013. Solving it was fun, though I find myself looping through similar data quite often.

Challenge:


Print the maximum beauty of strings.

Specifications:


The beauty of a string is the sum of the beauty of the letters within.

The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty.

Lettercase is irrelevant.

Your program should accept as its first argument a path to a filename.

Each line in this file has a sentence.

Print out the maximum beauty of each sentence.

This means calculate the maximum possible beauty a string can have.
e.g. In test case, "AbBCcC" assign 26 to C, as it occurs the most in the string, followed by 25 to B, and 24 to A. For a maximum beauty of 152.

Solution:

```
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class BeautifulStrings {
public static void main(String[] args) throws FileNotFoundException {
Scanner input = new Scanner(new File(args[0]));

while (input.hasNextLine()) {
printMaximumBeauty(input.nextLine());
}
}

private static void printMaximumBeauty(String line) {
System.out.println(
computeMaximumBeauty(line
.replaceAll("[^a-zA-Z]", "")
.toLowerCase()
.toCharArray()
)
);
}

private static int computeMaximumBeauty(char[] line) {
int beauty = 0;
int beautyVal = 26;
int count = 0;
Set uniqueCharacters = new HashSet<>();
List appearanceCounts = new ArrayList<>();

for (char c : line) {
uniqueCharacters.add(c);
}

for (char u : uniqueCharacters) {
for (char c : line) {
if (u == c) {

Unit testing

Hi again @Legato, I'll probably bug you with unit testing until you start writing them ;-)

@Test
public void test_ABbCcc() {
    assertEquals(152, computeMaxBeauty("ABbCcc"));
}

@Test
public void test_This_is_from_Facebook_Hacker_Cup_2013_() {
    assertEquals(551, computeMaxBeauty("This is from Facebook Hacker Cup 2013."));
}

@Test
public void test_Ignore_punctuation__please___() {
    assertEquals(491, computeMaxBeauty("Ignore punctuation, please :)"));
}

@Test
public void test_Sometimes_test_cases_are_hard_to_make_up_() {
    assertEquals(729, computeMaxBeauty("Sometimes, test cases are hard to make up."));
}

@Test
public void test_CodeReview_is_love__CodeReview_is_life_() {
    assertEquals(724, computeMaxBeauty("CodeReview is love. CodeReview is life."));
}

The first implementation

It's good that the logic is decomposed to 2 methods (as opposed to not decomposed at all).

The printMaximumBeauty method converts the input string to char[].
I think it would be better to pass the string to computeMaximumBeauty and let it do whatever it wants with it.
For the record, there's a trade-off when converting to a char[] as opposed to accessing characters with .charAt(index):

• Converting to char[] creates a new array, so doubles the space

• Accessing characters with .charAt(index) incurs a boundary check every time

The computeMaximumBeauty method is very inefficient:

• It iterates over the characters once to find unique ones

• For each unique character it iterates over the characters again to count

You could combine these two steps.

You also incur some performance penalty due to autoboxing / unboxing, but that may be negligible.

Lastly, don't declare variables at the top. Java is not C.
Declare variables the latest possible, and in the smallest scope possible.
For example count could be declared in the for loop where it's used,
and then you wouldn't need to reset it in every cycle.

The second implementation

This method counts the appearances better, by doing it one pass.
Note that this line will do two map lookups when c is already in the map:

beautyMap.containsKey(c) ? beautyMap.get(c) + 1 : 1

First in .containsKey, then again in .get.
To reduce the lookups, you can do one .get and a null-check.

When calculating the beauty, you iterate over entries, but use only the values:

for (Map.Entry e : valueSorted.entrySet()) {
    beauty += e.getValue() * beautyVal++;
}

If you don't need the keys, then it would be better to iterate over the values instead of the entries.
And if you don't need the keys here, then probably you don't need them at all.
So instead of a map, a list would have been enough, and probably simplify your logic.

This implementation also declares variables at the top, which is not so good.
And it also incurs some performance penalties due to autoboxing / unboxing.

Suggested implementation

Here's an alternative implementation that's simpler.
It uses the fact that there can be at most 26 unique values,
so the appearance counts can be stored in a simple int[].

private int computeMaxBeauty(String text) {
    String sanitized = text.replaceAll("[^a-zA-Z]", "").toLowerCase();

    int[] counts = new int[26];
    for (int i = 0; i = 0 && counts[i] > 0; --i) {
        sum += counts[i] * (i + 1);
    }
    return sum;
}

StackExchange Code Review Q#82163, answer score: 9