First Unique Character
Problem
Given a piece of text, find the position of the first character that appears exactly once in the whole text. Positions are counted from zero. Return -1 when every character shows up more than once.
Examples
Input: text = "reference"
Output: 2
Why: r and e both repeat later, so f is the first character that stands aloneInput: text = "aabb"
Output: -1
Why: every character has a twinInput: text = ""
Output: -1
Why: edge case, there is no character to reportHints
0 / 3
Whether a character is unique depends on the entire text, including what comes after it, so no single left-to-right decision can be made on first sight.
Separate the two questions: how often does each character occur, and which position comes first. The first question can be answered completely before the second one is asked.
Count every character in one pass. Then walk the text again in order and return the position of the first character whose count is one. Reaching the end without a hit means the answer is -1.
Solution
Uniqueness cannot be decided during a single forward pass, because a character seen once may still repeat later. Two passes solve it cleanly: the first builds a tally of every character, and the second walks the text in order and stops at the first character whose tally is one. Walking the text rather than the tally is what makes the answer the first position rather than an arbitrary one. Time is O(n) and space is O(k) for the distinct characters.
from collections import Counter
def first_unique_index(text):
counts = Counter(text) # one pass to tally every character
for i, ch in enumerate(text):
if counts[ch] == 1: # the earliest character with a tally of one
return i
return -1
print(first_unique_index("reference")) # -> 2
print(first_unique_index("aabb")) # -> -1
print(first_unique_index("")) # -> -1Stuck on the idea rather than the code? Frequency Counting covers it.