Leetcode - First Unique Character in a String

Question

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

My solution

public class FirstUniqueCharacter {

    public int firstUniqChar(String s) {
        LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();

        for (char c : s.toCharArray()) {
            if (Objects.isNull(map.get(c))) {
                map.put(c, 1);
            } else {
                int count = (Integer) map.get(c);
                map.put(c, ++count);
            }
        }

        for (Map.Entry e : map.entrySet()) {
            int value = (int) e.getValue();
            Character c = (Character) e.getKey();
            if (value == 1) {
                return s.indexOf(c);
            }
        }

        return -1;
    }
}

The statistics shows it’s still slower than 60% of the solutions submitted in terms of speed and space. How can I improve it? Any comments regarding code readibility are most welcome.

Answer 1

You don’t need Objects.isNull(...). Simply using != null would suffice, and avoids an extra function call so should be faster (unless the compiler can optimize the call out).

---

Your loop at the end is using raw types. You should use

for(Map.Entry<Character, Integer> e : map.entrySey()) {

instead, for type safety. Your castings then are unnecessary.

---

There is no need to fetch the character c = e.getKey() unless value == 1 is true; you can more that inside the if for a minor performance gain.

---

Counting the character occurrences is slightly dangerous: you could overflow an Integer, or even a Long with a long enough string. Simply flagging the character as “seen once” or “more than once” avoids the counting overflow bug.

---

The map.put(c, 1) call returns the previous value stored in the map, or null if no value was stored. Instead of fetching the value, testing whether it was present or not, and then storing another value, why not store & fetch in one operation? Then, if a value was already present, you can flag it as occurring twice (or more).

if( map.put(c, 1) != null )
    map.put(c, 2);

---

Since you are no longer counting, you don’t need a LinkedHashMap<Character, Integer>. You just have 3 states: not seen, seen once, and seen more than once. A Boolean can cover this. Boolean.TRUE is seen once (unique), Boolean.FALSE is seen more than once, and not present (null) is never seen.

LinkedHashMap<Character, Boolean> unique = new LinkedHashMap<>();

for(char c: ...) {
    if (unique.put(c, Boolean.TRUE) != null)
        unique.put(c, Boolean.FALSE);
}

We’ve saved a tiny bit of space, since we only have two Boolean objects, instead of several (possibly interned) Integer objects. Much more importantly, we’ve avoided auto boxing, so this should be much faster.

---

We are still wasting time storing both Boolean.TRUE and Boolean.FALSE successively on the third and subsequent occurrences of any character.

If we always store Boolean.FALSE, then on the first occurrence null will be returned. We can detect that and overwrite it with Boolean.TRUE instead, so the exceptional first occurrence has 2 map put operations, but subsequent occurrences only use 1 map put operation, for better performance.

    if (unique.put(c, Boolean.FALSE) == null)
        unique.put(c, Boolean.TRUE);

---

To truly gain speed and reduce memory usage, avoid clunky HashSet<> memory structures, and store the data yourself. You are told you can assume only lowercase letters are used, so you can use a new byte[26] array for “not seen”, “seen once”, and “seen multiple times” storage. And use a new char[26] array to maintain encounter order of “first seen” characters.

You can use a bit more memory and store the index of the first seen characters in a new int[26], so you can avoid the linear s.indexOf(c) search at the end. You could even use 0 for not seen, index+1 for seen once, and -1 for seen multiple times, and avoid the new byte[26] flag storage.

Answer 2

Having LinkedHashMap A and HashSet B.

For each character C in string S

• Map C to it's position in S to A.
• If adding C to B returns false
• Remove C from A.

Return value mapped to first element in A or -1 if A is empty.