Ytukyg

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 below 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.

I got 98.58% with this:-

public int firstUniqChar(String s) {

    int count = new int[122 - 96];

    final char chars = s.toCharArray();

    for (int i = 0; i < chars.length; i++) {

        count[chars[i] - 97]++;

    }

    for (int i = 0; i < chars.length; i++) {

        if (count[chars[i] - 97] == 1)

            return i;

    }

    return -1;

}

As @Ruakh says in a comment, the precise timings produced by leetcode are subject to a certain amount of randomness, so they should be taken with a grain of salt:

My impression is that LeetCode is doing an unscientific microbenchmark that might depend on random factors.

Still, it is possible to speed your first loop up quite a bit by getting rid of the tests. The following loop is functionally equivalent; although it sets the variables more often, changing the value of a local integer variable costs less than testing whether it is necessary to change:

for (char c : chars) {

  int mask = 1 << c - 'a';

  secondSpot |= mask & firstSpot;

  firstSpot |= mask;

}

(It's important that the assignment be in that order, so that the first one does nothing if the character hasn't yet been seen.)

Use this:

import java.util.Arrays;



class Solution {

    //  0x60 < 'a' < 'z' < 0x80

    private final byte bCounter = new byte[0x80];

    private final int iCounter = new int[0x80];



    public int firstUniqChar(String s) {

        int len = s.length();

        if ((len & 0xff) == len) {

            Arrays.fill(bCounter, 0x60, 0x80, (byte)-1);

            for (int i = 0; i < len; i++)

                bCounter[s.charAt(i)]++;

            for (int i = 0; i < len; i++)

                if (bCounter[s.charAt(i)] == 0)

                    return i;

        } else {

            Arrays.fill(iCounter, 0x60, 0x80, -1);

            for (int i = 0; i < len; i++)

                iCounter[s.charAt(i)]++;

            for (int i = 0; i < len; i++)

                if (iCounter[s.charAt(i)] == 0)

                    return i;

        }

        return -1;

    }

}