# Finding the most common character in a string

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


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.

• 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.

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;

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