How to Find First Unique Character in a String?

Given a string (you may assume it is lowercase letters only), your task is to find out the first unique letter and return its index. If it does not exist, return -1.

This puzzle is quite similar to this and this where you can use a static counter array to record the number of appearance for each letters (bin counting).

C++ Source Code: Find First Unique Character

The idea is to bin counting each character (lowercase letters) in a static array, and start checking from the start of the string, if the counting is 1 (unique), return its index. Otherwise, when reaching the end of the string, return -1.

class Solution {
public:
    int firstUniqChar(string s) {
        int cnt[26] = {0};
        for (auto c: s) {
            cnt[c - 97] ++;
        }
        for (auto i = 0; i < s.length(); i ++) {
            if (cnt[s[i] - 97] == 1) {
                return i;
            }
        }
        return -1;
    }
};

O(n) time and O(n) space complexity. Please note that the 97 is the ASCII code for the lowercase letter 'a', so minus 97 returns the correct index in the bin.

--EOF (The Ultimate Computing & Technology Blog) --