Code Implementation

class Solution:
    def firstUniqChar(self, s: str) -> int:
        from collections import Counter
        count = Counter(s)
        for idx, char in enumerate(s):
            if count[char] == 1:
                return idx
        return -1
      

class Solution {
public:
    int firstUniqChar(string s) {
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        for (int i = 0; i < s.size(); ++i) {
            if (count[s[i] - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
};
      

class Solution {
    public int firstUniqChar(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (count[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
}
      

var firstUniqChar = function(s) {
    const count = {};
    for (let char of s) {
        count[char] = (count[char] || 0) + 1;
    }
    for (let i = 0; i < s.length; i++) {
        if (count[s[i]] === 1) {
            return i;
        }
    }
    return -1;
};
      

Problem Description

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

The string s consists only of lowercase English letters. You must find the character that appears exactly once and is the earliest such character (i.e., has the smallest index). If no such character exists, return -1.

Constraints:

• 1 ≤ s.length ≤ 10⁵
• s consists of only lowercase English letters.

Thought Process

When approaching this problem, the first idea is to check each character in the string and see if it appears only once. The naive way would be to, for every character, scan the entire string and count its occurrences. However, this would result in a time-consuming solution, especially for long strings.

To optimize, we can realize that it's more efficient to count the frequency of each character in a single pass, and then, in a second pass, find the first character with a count of one. This avoids unnecessary repeated scans and leverages data structures for fast lookups.

The key shift is moving from a brute-force approach (checking every character against every other) to an optimized approach using counting (hash maps or arrays), which is much faster.

Solution Approach

• Step 1: Iterate through the string and count the occurrences of each character. Since the string consists only of lowercase English letters, we can use an array of size 26 or a hash map for counting.
• Step 2: After counting, iterate through the string again from left to right. For each character, check its count in the map or array.
• Step 3: The first character whose count is exactly one is the answer; return its index.
• Step 4: If no such character is found, return -1.

We use a hash map (or array) because it allows us to store and retrieve counts for each character in constant time. This makes both passes through the string efficient.

Example Walkthrough

Input: s = "leetcode"

1. First pass (counting):
   • 'l': 1
   • 'e': 3
   • 't': 1
   • 'c': 1
   • 'o': 1
   • 'd': 1
2. Second pass (find first unique):
   • Index 0, 'l': count is 1 → return 0

Result: The first unique character is 'l' at index 0.

Another example: s = "loveleetcode"

1. First pass:
   • 'l': 2
   • 'o': 2
   • 'v': 1
   • 'e': 4
   • 't': 1
   • 'c': 1
   • 'd': 1
2. Second pass:
   • Index 0, 'l': count is 2
   • Index 1, 'o': count is 2
   • Index 2, 'v': count is 1 → return 2

Result: The first unique character is 'v' at index 2.

Time and Space Complexity

Brute-force Approach:

• For each character, count how many times it appears by scanning the whole string.
• Time complexity: O(n²) where n is the length of the string.
• Space complexity: O(1) (no extra space except variables).

Optimized Approach (Counting):

• First pass: O(n) time to count all characters.
• Second pass: O(n) time to find the first unique character.
• Total time complexity: O(n).
• Space complexity: O(1), since the hash map or array size is fixed (26 for lowercase letters).

The optimized approach is much faster for large strings.

Summary

The "First Unique Character in a String" problem can be solved efficiently by counting character frequencies and then scanning for the first unique one. Using a hash map or array for counting allows us to check each character's count in constant time, resulting in a linear time solution. This approach is elegant because it separates counting and searching, making the code simple, fast, and easy to understand.