Skip to main content

387 - First Unique Character in a String

Difficulty: Easy | Pattern: Hash Map / Counting | Company tags: Amazon, Bloomberg, Microsoft, Google

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  ('l' appears only once, at index 0)

Example 2:

Input: s = "loveleetcode"
Output: 2  ('v' appears once, first at index 2)

Example 3:

Input: s = "aabb"
Output: -1

Algorithm Flow​

Approach: Two-Pass with Counter — O(n)​

from collections import Counter

def firstUniqChar(s: str) -> int:
    count = Counter(s)
    for i, c in enumerate(s):
        if count[c] == 1:
            return i
    return -1

Pass 1: Count frequency of each character. Pass 2: Scan left to right and return the index of the first character with count 1.

Alternative: Array of 26 — O(n)​

def firstUniqChar(s: str) -> int:
    freq = [0] * 26
    for c in s:
        freq[ord(c) - ord('a')] += 1
    for i, c in enumerate(s):
        if freq[ord(c) - ord('a')] == 1:
            return i
    return -1

Dry Run​

s = "loveleetcode"

Counts: l=2, o=2, v=1, e=4, t=1, c=1, d=1

Scan: l(2)→o(2)→v(1) → return index 2 ✓

Edge Cases​

  • Single character → return 0
  • All repeating → return -1
  • All unique → return 0 (first character)

Complexity​

  • Time: O(n) — two passes
  • Space: O(1) — at most 26 lowercase letters

Key Terms​

TermDefinition
Hash map countingUsing a dictionary/Counter to tally how many times each character appears in one pass.
Two-pass scanFirst pass builds frequency data, second pass uses it to answer the query in order.
Frequency arrayA fixed 26-length array alternative to a hash map when the alphabet is limited to lowercase letters.
Non-repeating characterA character whose total count across the string is exactly 1.

FAQ​

Q: Can this be solved in a single pass? A: Not with plain array scanning if you need the first index, since you don't know final counts until the string is fully read; however, an OrderedDict-based single-pass approach can track candidates and remove ones that repeat, effectively still visiting each character a bounded number of times.

Q: What if the string is empty? A: Return -1 immediately since there's no character to inspect.

Q: What if all characters repeat? A: The second pass never finds a count of 1, so the function correctly returns -1.

Q: How would this change if the alphabet included uppercase letters or Unicode? A: The 26-length array approach would need a hash map instead, since indexing by ord(c) - ord('a') no longer covers all possible characters.

Q: How is this different from Ransom Note (383)? A: Ransom Note compares counts between two strings; this problem only needs frequency within a single string, then a second scan to find the first count-1 character in original order.

Quick Revision​

  • Goal: find the index of the first character that appears exactly once; return -1 if none.
  • Pass 1: build a frequency count with Counter or a 26-length array.
  • Pass 2: scan left to right, return the first index where count == 1.
  • Time: O(n) for two linear passes; Space: O(1) since alphabet is fixed size.
  • Order matters — always scan original string order in pass 2, not the count structure's order.
  • Edge cases: empty string → -1; single character → 0; all unique → 0.
  • Pattern generalizes to any "first/last element satisfying a global frequency condition" problem.
  • 383 - Ransom Note — same hash-map counting technique applied to two strings.
  • 242 - Valid Anagram — character frequency comparison between two strings.
  • Longest Substring Without Repeating Characters — related character-frequency tracking with a sliding window.