💬 Discord
Sign In
NeetCode #82LC-387EasyArrays & Hashing
← Back to All Problems

#82 · #387 · First Unique Character in a String(字符串中的第一个唯一字符)

📌 Problem Statement & Constraints

Given a string s, find the first non-repeating character and return its index, or -1 if none exists. Constraints: 1 <= s.length <= 10^5, lowercase letters.

💡 Core Algorithmic Approaches

  1. Count the frequency of every character in one pass.
  2. Scan the string again in order and return the index of the first character with frequency 1.
  3. The second pass must iterate the string, not the counter, because the counter has no order information (and dict insertion order reflects first appearance, which happens to coincide here -- but relying on it is fragile).
  4. An alternative is a queue-based single pass, but the two-pass approach is simpler and equally O(n).

💻 Benchmark Python3 Implementation

class Solution:
    def firstUniqChar(self, s: str) -> int:
        from collections import Counter
        cnt = Counter(s)
        for i, ch in enumerate(s):     # scan the string to preserve order
            if cnt[ch] == 1:
                return i
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): two linear passes.
💾 Space Complexity
O(k) for the counter, k <= 26, so O(1) in terms of the alphabet.

⚠️ Interview Pitfalls & Follow-ups

  • Iterating the counter instead of the string: dict order is not guaranteed to be the first-appearance order in every language, and even in Python it is an implementation detail worth avoiding.
  • Returning the character instead of its index: the signature returns an index.
  • Using s.find(ch) inside the loop: O(n) per character, giving O(n^2).
  • Sorting the characters: order is the whole point, so sorting destroys the problem.