First Unique Character in a String

Patrick Leaton

Published: March 5, 2021, 10:33 p.m.

Problem Description

Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

Description is taken from https://leetcode.com/problems/first-unique-character-in-a-string/.

Problem Solution

#O(N) Time, O(1) Space

class Solution:

def firstUniqChar(self, s: str) -> int:

seen = {}

for char in s:

if char in seen:

seen[char] += 1

else:

seen[char] = 1

for i in range(0, len(s)):

if seen[s[i]] == 1:

return i

return -1

Problem Explanation

Let's break this question down real quick. A unique character means that the count of the character is singular, so we know that we are likely going to need to keep track of counts. "First" implies that there may be multiple characters with a singular count, so we need a character with a singular count with an index value that is lesser than the index values of all the other unique characters.

Knowing this, we may now find that we can solve this problem by using a hashmap to count the frequency of each character through one traversal, and then in the second traversal, we will reference the hashmap. The first character we find in the hashmap with a single frequency will be what we will return. If we don't return anything, then we don't have any unique characters so we will return a negative one.

Let's initialize the hashmap that we will use to mark how many times we have seen a character.

seen = {}

Then, we will make our first pass through the string. During each iteration, we will check if we have seen this character before. If we have, then we will increment its frequency in the hashmap.

for char in s:

if char in seen:

seen[char] += 1

If we have not, then we will place it in the hashmap with an initial frequency of one.

else:

seen[char] = 1

Now that we have counted the frequency of each character, we will make one more pass and during each iteration, if we see that we have a character with a single frequency, we will return its index.

for i in range(0, len(s)):

if seen[s[i]] == 1:

return i

If we finished our traversal and didn't return anything, then we never saw a character with a single frequency, so we will return a negative one.

return -1