First Unique Character in a String

Finding the first non‑repeating character in a string is a great warm‑up that combines practical string processing with frequency counting. In real‑world scenarios, this pattern appears when you need to identify the first distinct event in a log stream or the first unique user action in analytics data.

Problem Statement

Given a string s, return the index of the first non‑repeating character in s. If no such character exists, return –1.

1. Clarify Requirements Before Jumping Into Code

Let me confirm a few details before diving in

• Are we working with only lowercase English letters? Yes, assume a–z.

• Should the algorithm run in linear time if possible? Yes, optimal solutions target O(n).

• Can I use extra space for counts? A small fixed array or hash map is fine.

• What should I return if the string is empty? Return –1.

2. Identify the Category of the Question

This falls squarely into string manipulation with a frequency counting pattern. Tracking how often each character appears suggests a hash map or fixed‑size array. Once frequencies are known, a second pass identifies the first character with count 1.

3. Consider a Brute‑Force Approach to Understand the Problem

A naive strategy: for each index i, scan the entire string to count occurrences of s[i]. If count equals 1, return i. Pseudocode:

for i from 0 to n‑1:
  count = 0
  for j from 0 to n‑1:
    if s[j] == s[i]:
      count++
  if count == 1:
    return i
return ‑1

Time complexity O(n²), space O(1). Works, but too slow for large strings.

4. Brainstorm More Solutions

Better approach uses two passes

• First pass: build a frequency map (hash map or array[26]) in O(n).

• Second pass: iterate s again and return the first index where frequency is 1.

This yields O(n) time, O(1) extra space when using a 26‑element array.

Alternative: maintain insertion order in a linked hash map and scan entries, but that’s overkill here.

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Brute‑Force	O(n²)	O(1)	Simple	Too slow for large n
Hash Map Two‑Pass	O(n)	O(n)	Fast, clear	Uses hash map memory
Fixed‑Array Two‑Pass	O(n)	O(1) (26)	Fast, minimal extra memory	Assumes limited charset

Fixed‑array two‑pass is ideal given lowercase letters only.

6. Write Pseudocode to Structure Your Thoughts

function firstUniqChar(s):
  if s is empty:
    return ‑1

  create count array of size 26 initialized to 0

  for each character c in s:
    count[c − 'a']++

  for index i from 0 to length(s)−1:
    if count[s[i] − 'a'] == 1:
      return i

  return ‑1

7. Consider Edge Cases

• Empty string → returns –1

• Single character string → index 0

• All characters repeated, e.g. “aabb” → –1

• First character unique, e.g. “abcab” → 0

• Last character unique, e.g. “aabbc” → 4

8. Write Full Code Syntax

def first_unique_char(s: str) -> int:
    n = len(s)
    if n == 0:
        return -1

    counts = [0] * 26
    for ch in s:
        counts[ord(ch) - ord('a')] += 1

    for i, ch in enumerate(s):
        if counts[ord(ch) - ord('a')] == 1:
            return i
    return -1

9. Test Your Code

# Test 1: basic
assert first_unique_char("leetcode") == 0  # 'l'

# Test 2: unique in middle
assert first_unique_char("loveleetcode") == 2  # 'v'

# Test 3: no unique
assert first_unique_char("aabb") == -1

# Test 4: single character
assert first_unique_char("z") == 0

# Test 5: empty string
assert first_unique_char("") == -1

print("All tests passed!")

10. Key Lessons to Remember for Future Questions

• When you need to count occurrences, a two‑pass frequency array or hash map is often the fastest and simplest solution. First‑pass/second‑pass is a common pattern for problems requiring aggregation then selection.

• Quick length or empty checks can short‑circuit edge cases.

• Always clarify character set constraints - fixed‑array solutions rely on limited alphabets.

Happy Coding!