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

• rolfl: What happens if the two longest unique words are the same length?
• JavaDeveloper: I should have realized it, also documented it.

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.

• 200_success: Sorting would take O(n log n) time, though. The current solution is O(n).
• David Harkness: O(n log n) on the unique word lengths (10? 15?) is better than O(n) on the number of unique words (1,000? 1,000,000?).

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.

• Ravinder Reddy: What if, if the most latest added max length word is required?
• Yuushi: Change the comparator. After the first 2 checks, you'll have that s2 must be the same length as s1. Check if they are equal (s2.equals(s1)), and if not, return -1 (which will put s2 ahead of s1).
• 200_success: final enforces no guarantees about the contents of the List. It just prevents this function from rebinding words internally. I wouldn't bother.
• Yuushi: @200_success Thanks, I always have to be reminded that final != const when I come back to Java-land.