Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

file 56 lines (47 sloc) 1.586 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
'''
First Unrepeated Character In A String
April 30, 2013

We have today another exercise from our never-ending supply of interview
questions:

Given a string, find the first character that appears only once in the
string. For instance, given the string "aabbcddd", the first character
that appears only once is the "c" found at the 4th character in the string,
counting from 0. Be sure that your program properly handles the case that
all characters appear more than once.

Your task is to write a program that finds the first unrepeated character in a
string, and its index in the string. When you are finished, you are welcome to
read or run a suggested solution, or to post your own solution or discuss the
exercise in the comments below.
'''

def first(s):
'''
Return a tuple (index, character) of the first unique character in the
string s.

Note:
Tried to make it as fast as possible in run time...
O(2n) => O(n)
But uses the same in additional memory.
'''
visited = {}
unique_idx = {}

for idx, c in enumerate(s):
if not c in visited:
unique_idx[c] = idx
visited[c] = 1

else:
if c in unique_idx:
del unique_idx[c]

if not unique_idx:
return None
else:
# make sure we return the first one in order...since no order gaurantee
# from hashsets
for idx, c in enumerate(s):
if c in unique_idx:
return (idx, c)

print first("c") == (0, 'c')
print first("caa") == (0, 'c')
print first("aac") == (2, 'c')
print first("aabbcddd") == (4, 'c')
print first("aabbcddde") == (4, 'c')
print first("aabbddd") == None
Something went wrong with that request. Please try again.