Leetcode - First Unique Character in a String

Question

Given a string, find the first non-repeating character in it and return its 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 move 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

Pay attention to Constraints

While cracking algorithmic problems, pay very close attention to the constraints of the problem at hand. They can often give valuable clues on how to attack the problem.

^{If you're attending an interview, and the interviewer didn't mention any input constraints, it's always good to raise a question about it.}

According to the problem statement on Leetcode the input string is guaranteed to contain only lowercase English letters. I.e. we have only up to 26 unique characters in the string.

^{And also each character is guaranteed to be represented by a single char, which is not the case with some languages, but you're unlikely to encounter such scenario when tasked with an algorithmic problem.}

Using String.toCharArray() is Costly

This method has linear time complexity (not constant) and requires additional O(n) space.

Before Java 9 when the strings were backed by a char[], the method toCharArray() would return its copy (because exposing the internal storage will break the encapsulation and undermine the immutability of String). And starting from Java 9 so-called compact strings backed by byte[] were introduced, and toCharArray() generates char[] on demand based on the encoding of a particular string (which for now is either UTF-16 or LATIN1).

For a large string, the memory footprint of the code you shared will be dominated by the char[] produced by toCharArray(), not by the map of characters which is confined to at most 26 entries.

Instead of paying this cost, you can simply iterate over the character indices and reduce the space complexity from O(n) to O(1).

Leveraging the problem constraints

This problem can be solved in a single iteration over the given string and by utilizing O(1) additional space. More precisely, by using a single integer array that has 26 elements, storing character indices.

Here's how it can be implemented:

private static final int NOT_PRESENT = -1;
private static final int DUPLICATE   = -2;
private static final char MIN_LETTER = 'a';


public static int firstUniqueChar(String input) {
    return getFirst(letterIndices(input));
}

private static int[] letterIndices(String input) {
    final int[] indices = initializeIndices();
    
    for (int i = 0; i < input.length(); i++) {
        int position      = input.charAt(i) - MIN_LETTER;
        indices[position] = indices[position] == NOT_PRESENT ? i : DUPLICATE;
    }
    return indices;
}

private static int[] initializeIndices() {
    int[] indices = new int[26];
    Arrays.fill(indices, NOT_PRESENT);
    return indices;
}

private static int getFirst(final int[] indices) {
    int first = NOT_PRESENT;
    
    for (int i: indices) {
        if (i == DUPLICATE || i == NOT_PRESENT) continue;
        
        first = first == NOT_PRESENT ? i : Math.min(first, i);
    }
    return first;
}

Note: one might ask what about all these method calls, aren't they causing performance overhead? (and the interviewer might ask it as well to test your knowledge)

To understand how to answer this question, you need to have some knowledge about JIT compilation. In short, JIT compiler identifies the most frequently utilized code parts (hotspots), then inlines method calls and reorders instructions to optimize performance. The shorter a method is, the quicker it gets optimized. There's no advantage neither in piling code into one method, no in making use of built-in functionality offered by the JDK (such as Math.min() and Arrays.fill()).

Minor points

• "Never abbrev" (a joke from Martin Fowler). Don't skimp on characters, use proper names, code quality has no nothing to do with number of keystrokes spared.

firstUniqChar -> firstUniqueChar

Leetcode platform will not allow you this change, since it'll be looking for the method firstUniqChar. But it doesn't invalidate the point. You can define a properly named method and call it from the one declared by Leetcode. Naming code elements is not an easy task, and requires practice.

---

• There's no reason is for firstUniqChar to be an instance method (again, Leetcode specific thing, the remedy is the same as mentioned above).

---

• There's nothing in bad performing an explicit null-check

^{Please, don't confuse what I'm saying with a situation when application is suffering from null-infestation and there are null-checks all over the place. The point is that by itself null-check is not evil, the many JDK methods returning null and we need to dial with it.}

Method Objects.isNull() along with some other methods was introduced in Java 8 to serve as a predicate Objects::isNull. It's not useful when you're not dialing with functional interfaces.

Compare this

if (Objects.isNull(map.get(c))) { ... }

with this

if (map.get(c) == null) { ... }

And it becomes clear more clear that it's basically a Map.containsKey() check in disguise, and there's no need to mess with null.

---

• Map.merge()

Whenever you find yourself writing the following conditional logic: if a key is absent, then put some value, otherwise update existing one; then it's good use case for Map.merge().

So, this

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

can be changed to this

var charCount = new LinkedHashMap<Character, Integer>();
        
for (int i = 0; i < s.length(); i++) {
    charCount.merge(s.charAt(i), 1, Integer::sum);
}

---

• Proper names

The name of the code element should communicate its purpose to the reader of the code.

The name map fails to do so. It doesn't reveal the purpose of the variable. No doubt, it's a map, it has no chance to be anything but a map. It's redundant to include type in the name, Java is a statically typed language, hence if you'll to treat this variable as, let's LocalTime, Java compiler will tell you (and your IDE will tell as well).

Instead, the name should tell what this map is intended to store. Therefore, consider names like charCount, countByChar, etc.

Answer 3

In Java Use the FirstIndexOf() and LastIndexOf() if these both return the same number then its the unique character in the statring of the string return the index of it break the loop. This is the fastest the solution.

class Solution {
public int firstUniqChar(String s) {
    for (int i = 0; i < s.length(); i++) {
        int first = s.indexOf(s.charAt(i));
        int last = s.lastIndexOf(s.charAt(i));
        if (first == last) {
            return i;
        }