Unique character lookup

Question

I'm solving 387. First Unique Character in a String LeetCode problem defined as:

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.

Taking advantage of the input being fully lowercase ASCII I created two bit vectors to track when we encounter a character for the first and second time.

Can this code be improved further? LeetCode says that below code is better than 94.33% solutions. What else could have been done by the last 5.67% solutions that they were better?

class Solution {

  public int firstUniqChar(String s) {
    int firstSpot = 0;
    int secondSpot = 0;
    char[] chars = s.toCharArray();

    for (char c : chars) {
      int mask = 1 << c - 'a';
      if ((firstSpot & mask) == 0) {
        firstSpot |= mask;
      } else if ((secondSpot & mask) == 0) {
        secondSpot |= mask;
      }
    }

    int i = 0;
    for (char c : chars) {
      int mask = 1 << c - 'a';
      if ((secondSpot & mask) == 0) {
         return i;
      }
      i++;
    }
    return -1;
  }

}

Are there tricks that can be done to improve the LeetCode score? It seems that enhanced for-each loop performs better than standard for loop but I can't prove it. It's an observation based on few of my previous submissions.

Answer 1

• When in doubt, profile. We may theorize about possible optimizations, but only the profiler can definitely say where the program does spend time.

• That said,

  • the first/second spot logic looks suboptimal. Consider

    if ((firstSpot & mask) != 0) {
        secondSpot |= mask;
    } else {
        firstSpot |= mask;
    }
    

  (using else may also be redundant).

  • It is unclear (to me) how for (char c : chars) over the char array fares against other techniques. This could be an entertaining reading.

  Yet again, profile.

• Strictly speaking, the challenge only says the string contain only lowercase letters, but does not specify the locale.

Answer 2

Some suggestions:

• You could get rid of the class and put the entire method contents within your main method; that'll at least get rid of an instantiation.
• I'm not sure whether 'a' is converted to an integer at compilation time or runtime. Try using 0x61 instead.
• You can avoid converting to a char array.

Answer 3

You don’t need to check if the second spot has been filled in; just unconditionally set it.

if ((firstSpot & mask) == 0) {
    firstSpot |= mask;
} else {
    secondSpot |= mask;
}

---

Avoiding branching usually helps.

secondSpot |= mask & firstSpot; // sets second spot bit unless first spot bit is still zero
firstSpot  |= mask;

---

After the first loop finishes, if firstSpot == secondSpot, you can immediately return -1

Answer 4

Taking advantage of the input being fully lowercase ASCII

While it says that all characters are lowercase it doesn't say anything about ASCII. Given that it passed the tests that was okay, but generally lowercase doesn't imply ASCII.

I created two bit vectors to track when we encounter a character for the first and second time.

And that really requires the input to be ASCII. Because char can hold any value between 0 and 65535 the << might not be safe to use, I'm not a Java programmer but it could result in an exception, an unwanted result or undefined behavior.

But if it's just ASCII characters between 'a' and 'a' + 31 the approach will work.

Can this code be improved further? LeetCode says that below code is better than 94.33% solutions. What else could have been done by the last 5.67% solutions that they were better?

It seems like your definition of "improvement" is "better performance". But that again is probably not how every programmer defines "improvement".

As far as I see it:

• You don't have any comments,
• you don't have tests,
• your variables have odd names. For example: firstSpot is a weird name for a bitarray that represents if a character has been found once, ...
• you don't have benchmarks

So my personal opinion is: There's lots of room for improvement.

---

I also have some thoughts about the algorithm and how it could be improved. As said I'm not a Java programmer so I'm just sharing some thoughts:

• You iterate over the string three times while it would be possible to iterate only once. You could create an array of integers (26 elements long) to store the first occurrence of each character and after the loop you look at the elements that only occurred once and then take the minimum of the indices. Since you iterate with index you can remove the toCharArray and index into the string directly (which incidentally may be a faster way to iterate over the string altogether, according to this StackOverflow Q+A).

• In case there is no single character you might even stop the loop early. As soon as your secondSpot bitarray contains an entry for all ASCII characters you can immediately return -1.

• As the others mentioned you could even drop some of the "branches" inside the loop which may give some performance improvement.

Answer 5

I'd use a dictionary. Loop once over the characters in the string. For each found character, create an entry in the dictionary, the character being the key, the value being the index. If a character exists in the dictionary, set the value to [length of word] + 1. When all characters are seen, loop over the dictionary. Pick the least (first by my testing) index encountered less than [length of word] + 1 and return it. If no value is returned, return -1.

Here is my shot (admittedly in c#).

int firstUniqCharInString(string s)
        {
            Dictionary<char, int> seen = new Dictionary<char, int>();
            int t = -1; 
            foreach (char c in s)
            {
                t++;
                if (seen.ContainsKey(c))
                {
                    seen[c] = s.Length + 1;
                }
                else
                {
                    seen.Add(c, t); 
                }

            }
            int len = s.Length + 1; 
            foreach(KeyValuePair<char, int> pair in seen)
            {
                if(pair.Value < len) {
                    return pair.Value;
                }
            }
            return (-1);
        }