"Find the First Non Duplicate Character in a String", understanding HashTable vs. HashMap to guarantee insert order?

Question

I was doing this problem on Firecode.io where:

firstNonRepeatedCharacter( "abcdcd" ) --> 'a'
firstNonRepeatedCharacter( "cbcd" ) --> 'b'
firstNonRepeatedCharacter( "cdcd" ) --> null

The solution I came up with was:

public static Character firstNonRepeatedCharacter(String str) {
    if (str == null) return null;

    Hashtable<Character, Integer> map = new Hashtable<Character, Integer>();

    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (map.containsKey(c)) {
            map.put(c, map.get(c) + 1);
        } else {
            map.put(c, 1);
        }

    }

    for (Character key : map.keySet()) {
        if (map.get(key) == 1) return key;
    }

    return null;
}

This failed for the first test case and got:

firstNonRepeatedCharacter( "abcdcd" ) --> 'b'  // 'a' is correct

I realized I was assuming insert order, so I gave HashMap a try:

Map<Character, Integer> map = new HashMap<Character, Integer>();

which ended up passing all the cases.

Based on what I read however, HashMap should often be used over Hashtable, but HashMap doesn't even guarantee support order, and LinkedHashMap does. Is this correct? I just got lucky with the test cases and should be using LinkedHashMap?

The only reason to use `Hashtable` is if you're 85 years old and haven't come out of a cave since 1999 — Abhijit Sarkar, Aug 30 '17 at 02:04
@AbhijitSarkar Or if you're working with an API developed in a cave in 1999 :D — shmosel, Aug 30 '17 at 02:11
@AbhijitSarkar One of the problems on Firecode.io actually suggested a `Hashtable`... so considering I don't know Java and just wanted whatever was the idea of a "map" I started using `Hashtable` for problems that followed where I needed some mapping, which led to this discovery. :D — atkayla, Aug 30 '17 at 02:22
I don't know about firecode.io but every man and his dog had a blog these days. If you take them on face value without thinking...well, you'll end up in knee-deep to very deep p00p — Abhijit Sarkar, Aug 30 '17 at 02:25

score 0 · Answer 1 · answered Aug 30 '17 at 02:08

As you suggested, using LinkedHashMap would be very helpful here, because it keeps track of the insertion order of the key value pairs which get inserted into the map. So all you need to do is to just keep a counter of how many times you have seen each letter. When you insert a character, increment the counter, unless it were never seen before, in which you case you assign a value of one. Then, walk down the list, in insertion order, and return the first character which appeared only once. Here is a working implementation:

public static Character firstNonRepeatedCharacter(String str) {
    if (str == null) return null;

    // use a LinkedHashMap, which maintains insertion order
    // keep a counter of how many times a character is observed, which defaults to 1
    // for characters never seen before
    LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
    for (int i = 0; i < str.length(); i++) {
        Integer cnt = map.get(str.charAt(i));
        map.put(str.charAt(i), cnt == null ? 1 : cnt.intValue() + 1);
    }

    // now just walk the list, in insertion order, and return the first key
    // whose value is 1 (indicating that it never got repeated)
    for (Map.Entry<Character, Integer> entry : map.entrySet()) {
        if (entry.getValue() == 1) {
            return entry.getKey();
        }
    }

    // return null if no such key appearing only once occurred in the string
    return null;
}

Demo here:

"Find the First Non Duplicate Character in a String", understanding HashTable vs. HashMap to guarantee insert order?

1 Answers1

Rextester