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);
 }
}