Find the longest unique string in the input list

Question

Given a list, find the longest non-repeating (in other words I mean unique) string in the input list. Looking for code review, pointers on best practices, optimizations etc.

public final class LongestUniqueWord {

    /*
     * do not initialize this class
     */
    private LongestUniqueWord( ) {}


    /**
     * Returns the longest non-repeating(unique) word in the list.
     * If each word repeats then return null.
     * 
     * 
     * @param words the list of words of a news paper.
     * @return      the longest unique word.
     * @throws  IllegalArgumentException  if input size is 0.
     * @throws  NPE                       if the input is null. 
     */
    public static String longestUniqueWord (List<String> words) {
        if (words.size() == 0) throw new IllegalArgumentException("The array should not be empty.");

        final Map<String, Boolean> uniqueWords = new HashMap<String, Boolean>();

        for (String word : words) {
            if (uniqueWords.containsKey(word)) {
                uniqueWords.put(word, false);
            } else {
                uniqueWords.put(word, true);
            }
        }

        int maxLength = 0;
        String longestUniqueWord = null;
        for (Entry<String, Boolean> entry : uniqueWords.entrySet()) {
            if (entry.getValue() && entry.getKey().length() > maxLength) {
                longestUniqueWord = entry.getKey();
                maxLength = longestUniqueWord.length();
            }
        }

        return longestUniqueWord;
    }


    public static void main(String[] args) {
        List<String> newsPaper = new ArrayList<String>();
        newsPaper.add("Jack");
        newsPaper.add("In");
        newsPaper.add("In");
        newsPaper.add("The");
        newsPaper.add("The");
        newsPaper.add("Box");

        System.out.println("Expected: Jack, Actual: "  + longestUniqueWord(newsPaper));

        newsPaper.add("Jack");
        System.out.println("Expected: Box, Actual: " + longestUniqueWord(newsPaper));
    }

}

Answer 1

It looks fine, with the caveat that the answer is arbitrary if there are multiple unique words of the same maximal length. The code is easy to follow, with clear and concise naming. The algorithm is O(n), which cannot be improved upon significantly. Alternate approaches are possible, as pointed out by the other answers, but they aren't necessarily better than the existing code. Therefore, in my opinion, this is one of those cases where the solution is good enough to leave alone.

Answer 2

I'm on my phone so can only give pointers.

• In the first loop you can use Map.get and switch on its value:
  1. null: put True and add to wordsByLength
  2. True: put False and remove from wordsByLength
  3. False: do nothing

Map<Integer, Set<String>> wordsByLength tracks unique word sets, one per word length. It maps word length to a set of unique words. Whenever a new word appears in 1 above, add it to the set. When it is seen again for the first time in 2, remove it.

Next sort those entries by their keys (word length) in reverse and pull the first word from the first set.

Note that you may end up with ties of same-length words. The standard set will return an undefined "first" word. That may be okay.

Answer 3

Your solution is pretty good in general, although I'm going to outline a slightly different approach.

Firstly, as an aside, this method clearly isn't intended to modify the words list that is passed in, so let's make that final:

public static String longestUniqueWord (final List<String> words)

Secondly, we can (potentially) cut down on the work required but storing the pairs in a TreeMap. This will keep them in sorted order.

Map<String, Boolean> unique = new TreeMap<String, Boolean>(new Comparator<String>() {
    public int compare(String s1, String s2)
    {
        if(s1.length() > s2.length()) return -1;
        else if(s1.length() < s2.length()) return 1;
        return s2.compareTo(s1);
    }
});

Here, we create a TreeMap which orders its elements based on the given Comparator. This comparator says that longer strings come earlier in the set, and if two strings have the same length, then we just go back to comparing them lexicographically. Note that this gives you flexibility to easily change how you want to deal with ties.

Insertion is pretty much the same.

for(String word : words) {
    if(unique.containsKey(word)) {
        unique.put(word, false);
    } else {
        unique.put(word, true);
    }
}

However, iteration is now (potentially) faster: if the longest string is unique, this will happen immediately, instead of having to loop through the entire Map.

for(Map.Entry<String, Boolean> entry : unique.entrySet()) {
    if(entry.getValue()) {
        return entry.getKey();
    }
}

Of course, the tradeoff with this approach is that TreeMap is O(log n) instead of (amortized) O(1), but this could potentially be faster depending on expected input.