Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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"));
share|improve this question

2 Answers 2

up vote 5 down vote accepted

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.
share|improve this answer

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);
    }
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.