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.