DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

First Unique Character in a String

easyArrays and hashing

Problem statement

You are given a string s of lowercase English letters. Find the first character that appears exactly once in the whole string and return its index. If every character repeats, return -1.

Examples

Example 1

Input: s = "nginx"

Output: 1

Explanation: n appears twice. g at index 1 appears once, and it is the first such character.

Example 2

Input: s = "abab"

Output: -1

Explanation: Both a and b appear twice.

Hints

Approach

Two passes. The first pass counts every letter. The second pass walks the string in order and returns the first index whose letter has a count of 1.

  1. Make 26 counters.
  2. Pass 1: increment the counter for each letter.
  3. Pass 2: for each index, if its letter's count is 1, return the index.
  4. Return -1.

The second pass goes over the string, not over the alphabet, because "first" means first by position in s. The counter array has a fixed size of 26, so extra space is O(1).

ComplexityTime O(n)Space O(1)
Python
class Solution:
def firstUniqChar(self, s: str) -> int:
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

Follow-up questions

  • Return the first unique character after each new character in a stream.
  • Return the first character that appears exactly k times.

Frequently asked questions

Because it might appear again later. In "nginx", the first n looks new at index 0 but repeats at index 3. You need the full count before deciding.

Keep a count per character plus a queue of candidates in arrival order. Drop from the front of the queue while the front's count is above 1. The front is then the first unique character so far.

It is the same two-pass idea as finding the first request ID or error code in a log that occurs only once, for example a one-off failure buried among repeated retries. Count first, then scan in time order.