387. First Unique Character in a String

Description

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1. The problem asks for the position of the first character that appears exactly once in the string, considering its left-to-right order.

Intuition

To determine the first unique character, we need to count the occurrences of each character in the string. If a character appears only once, it is a candidate for being the "first unique character." The challenge is to efficiently keep track of character counts and then identify the first one with a count of 1.

Approach

1. Counting Frequencies: We traverse the string and count how many times each character appears using a hash map (or dictionary).
2. Identifying the Unique Character: After counting the frequencies, we iterate through the string again, checking the count of each character. The first character with a count of 1 is our answer.
3. Returning the Index: Return the index of the first unique character. If no such character exists, return -1.

Steps:

1. Create a hash map to store the frequency of each character.
2. Iterate through the string to populate the hash map with character counts.
3. Traverse the string again to find the first character with a count of 1 in the hash map.
4. Return its index or -1 if no such character exists.

Complexity

Time Complexity:

O(n), where n is the length of the string. We perform two passes through the string: one for counting and one for identifying the first unique character.

Space Complexity:

O(1), because the hash map holds at most 26 key-value pairs (for lowercase English letters).

Code

C++

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map charCount;

        // Count occurrences of each character
        for (char c : s) {
            charCount[c]++;
        }

        // Find the first character that occurs only once
        for (int i = 0; i < s.size(); i++) {
            if (charCount[s[i]] == 1) {
                return i;
            }
        }

        return -1;
    }
};

Python

class Solution:
    def firstUniqChar(self, s: str) -> int:
        char_count = {}

        # Count occurrences of each character
        for c in s:
            if c not in char_count:
                char_count[c] = 0
            char_count[c] += 1

        # Find the first character that occurs only once
        for i in range(len(s)):
            if char_count[s[i]] == 1:
                return i

        return -1

Java

class Solution {
    public int firstUniqChar(String s) {
        Map charCount = new HashMap<>();

        // Count occurrences of each character
        for (char c : s.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }

        // Find the first character that occurs only once
        for (int i = 0; i < s.length(); i++) {
            if (charCount.get(s.charAt(i)) == 1) {
                return i;
            }
        }

        return -1;
    }
}

JavaScript

var firstUniqChar = function (s) {
    s = s.split('')
    let map = {}
    for (let i of s) {
        if (!map[i]) map[i] = 0
        map[i] += 1
    }

    for (let i in s) {
        if (map[s[i]] === 1) return i
    }

    return -1
};