Finding the most common character in a string

Question

I have started to try and work out the TopCoder problems. The "StringDup" problem asks us to:

Create a class called StringDup. Given a string made up of ONLY letters and digits, determine which character is repeated the most in the string ('A' is different than 'a'). If there is a tie, the character which appears first in the string (from left to right) should be returned.

Is there any way I can make my solution better or more efficient? Is there something that I have missed? I'm new to Java and I thought this would be a good way to learn.

public class StringDup {

    public char getMax(String word)
    {
        int characterCount = 0;
        int maxCharacter = 0;
        char maxCharacterChar = '.';

        char[] cArray = word.toCharArray();

        for(int i =0; i < cArray.length; i++)
        {
            int characterASCII = (int)cArray[i];
            characterCount = 0;

            //System.out.print("Chracter ASCII: " + characterASCII + "\n");
            for(int x = 0; x < cArray.length; x++)
            {
                if(characterASCII == (int)cArray[x])
                {
                    characterCount ++;
                    //System.out.print("Character Count for " + characterASCII + " " +  characterCount  + "\n");
                    if(characterCount > maxCharacter)
                    {
                        maxCharacter = characterCount;
                        maxCharacterChar = cArray[i];
                    }
                }
            }
        }
        return maxCharacterChar;
    }
}

It is called using the main method.

StringDup frequentChar = new StringDup();
System.out.print(frequentChar.getMax("sssdkljgh"));

Answer 1

Your algorithm has two loops, and that's really not necessary.

This question is looking for a special 'trick' to be done.... and that trick is to process the data in reverse order....

Consider this loop:

public static char getMax(String word) {
    if (word == null || word.isEmpty()) {
        throw new IllegalArgumentException("input word must have non-empty value.");
    }
    char maxchar = ' ';
    int maxcnt = 0;
    // if you are confident that your input will be only ascii, then this array can be size 128.
    int[] charcnt = new int[Character.MAX_VALUE + 1];
    for (int i = word.length() - 1; i >= 0; i--) {
        char ch = word.charAt(i);
        // increment this character's cnt and compare it to our max.
        if (++charcnt[ch] >= maxcnt) {
            maxcnt = charcnt[ch];
            maxchar = ch;
        }
    }
    return maxchar;
}

note the following things:

• validate the input.
• create an array of counters for each character.
• work backwards... if this is the max count (or equal to it) then we have a new winner.
• there is no validation on the input characters .... you should probably limit the chars to the a-zA-Z0-9 set that is specified.... the solution above will work for any String.

Some additional notes....

• in Java, the standard code style puts the opening { brace on the same line as the block declaration (if condition, method declaration, etc.) Putting the brace on a new line is a C thing to do, and is frowned upon.
• x is not a good variable name for anything unless it is a co-ordinate in a multidimensional array (normally linked with (x, y, ...) ). In your use case, you should use the variable j because that is the one that by convention is used inside the i loop.

Answer 2

Currently it returns . in case of an invalid input (empty string, for example). It's not in the specification, so I think it shouldn't do that. Crash early. It is rather a bug in the client code when it calls the method with invalid input. Clients might produce bigger side-effect on a non-expected . result. I'd throw an IllegalStateException here. See: The Pragmatic Programmer: From Journeyman to Master by Andrew Hunt and David Thomas: Dead Programs Tell No Lies.

If you're allowed to use external libraries you could write it in a higher level of abstraction with Guava's Multisets and Iterables:

import static com.google.common.base.Preconditions.checkArgument;

import java.util.List;

import org.apache.commons.lang3.StringUtils;

import com.google.common.base.CharMatcher;
import com.google.common.base.Predicate;
import com.google.common.collect.Iterables;
import com.google.common.collect.LinkedHashMultiset;
import com.google.common.collect.Multiset;
import com.google.common.collect.Multisets;
import com.google.common.primitives.Chars;

public class StringDup {

    public char getMax(final String word) {
        checkArgument(StringUtils.isNotEmpty(word), 
            "empty input is not allowed");

        final Predicate<Character> allValidPredicate 
                = new Predicate<Character>() {
            @Override
            public boolean apply(final Character c) {
                return CharMatcher.JAVA_LETTER_OR_DIGIT.matches(c);
            }
        };

        final List<Character> inputCharList 
            = Chars.asList(word.toCharArray());
        final Iterable<Character> validInputChars 
            = Iterables.filter(inputCharList, allValidPredicate);
        final Multiset<Character> countedChars 
            = LinkedHashMultiset.create(validInputChars);
        checkArgument(!countedChars.isEmpty(), 
            "Input does not contain any valid chars: %s", word);
        final Multiset<Character> highestCountFirst 
            = Multisets.copyHighestCountFirst(countedChars);
        return highestCountFirst.iterator().next();
    }
}

Finally, a few unit tests with JUnit to make sure it works as intended:

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class StringDupTest {

    @Test(expected = IllegalArgumentException.class)
    public void testNullInput() throws Exception {
        getMax(null);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testEmptyStringInput() throws Exception {
        getMax("");
    }

    @Test
    public void test() {
        assertEquals('h', getMax("asdfffhjhhhhx"));
        assertEquals('f', getMax("asdfffhj#hfhhx"));
        assertEquals('A', getMax("AAaa"));
        assertEquals('a', getMax("AAaaa"));
        assertEquals('a', getMax("a"));
        assertEquals('a', getMax("a2"));
        assertEquals('2', getMax("a22"));
    }

    @Test(expected = IllegalArgumentException.class)
    public void testOnlyInvalidChars() throws Exception {
        getMax("#");
    }

    private char getMax(final String input) {
        return new StringDup().getMax(input);
    }
}