0387 - First Unique Character in a String (Easy)

Problem Link

https://leetcode.com/problems/first-unique-character-in-a-string/

Problem Statement

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:

Input: s = "leetcode"
Output: 0

Example 2:

Input: s = "loveleetcode"
Output: 2

Example 3:

Input: s = "aabb"
Output: -1

Constraints:

• 1 <= s.length <= 10^5
• s consists of only lowercase English letters.

Approach 1: Frequency Count

We can solve this problem in a linear time. We iterate the string and count the frequency of each character. This would takes $O(n)$. Then we go through the string again and check the frequency. If the frequency is $1$, that means it is unique. We can return the result at the first occurrence or return $-1$ if there is no such case.

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

class Solution {
public:
    __attribute__((no_sanitize("address")))
    static int firstUniqChar(const string& s) {
        array<int, 32> counts = {};
        for (char ch : s) ++counts[ch & 0x1f];
        for (int i = 0; i < s.size(); ++i) {
            if (counts[s[i] & 0x1f] == 1) return i;
        }
        return -1;
    }
};