First Unique Character in a String
<p>Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.</p>

<pre><code>first_unique('leetcode')  # 0
first_unique('loveleetcode')  # 2
</code></pre>

<p>I came up with the following solution.  How can I make it more efficient for very long input strings?</p>

<pre><code>def first_unique(self, s):
    if s == '':
        return -1

    for item in s:
        if s.count(item) == 1:
            return s.index(item)
            break

    return -1
</code></pre>

<p>The idea in this solution is to use a pair of defaultdicts. The first one contains an integer count of each character and the second contains the index location of the latest character read.</p>

<p>After reading all of the characters, a list comprehension is used to find all of those that only occurred once (<code>result</code>).  The minimum index locations of these characters (found in our other defaultdict <code>order</code>) will give us the first index location of non-repeating characters.</p>

<pre><code>from collections import defaultdict
# To Create random string:
from string import ascii_lowercase
from random import choice, randint, seed

# Create a random sentence of 1000 words (1-8 characters each).
seed(0)
gibberish = ' '.join(''.join(choice(ascii_lowercase) 
                             for _ in range(randint(1, 8))) 
                     for _ in range(1000))
print(len(gibberish))
# Output: 5614

# Solution.
def first_unique(s):
    dd = defaultdict(int)
    order = defaultdict(int)
    for n, c in enumerate(s):
        dd[c] += 1
        order[c] = n
    result = [order[c] for c in dd if dd[c] == 1]
    return min(result) if result else -1
</code></pre>

<h1>Timings</h1>

<pre><code>%timeit first_unique(gibberish)
100 loops, best of 3: 2.13 ms per loop

@wim solution:
%timeit first_unique(gibberish)
100 loops, best of 3: 5.06 ms per loop

@PatrickHaugh solution (which is much easier to understand than mine):
%timeit first_unique(gibberish)
100 loops, best of 3: 4.2 ms per loop

@BPL solution:
%timeit f1(gibberish)
10 loops, best of 3: 39.2 ms per loop
%timeit f2(gibberish)
1000 loops, best of 3: 890 Âµs per loop
</code></pre>

<p>Using a much shorter sentence of twenty words (133 characters):</p>

<pre><code>%timeit first_unique(gibberish)
10000 loops, best of 3: 62.8 Âµs per loop

@wim solution:
%timeit first_unique(gibberish)
10000 loops, best of 3: 169 Âµs per loop

@PatrickHaugh solution:
%timeit first_unique(gibberish)
10000 loops, best of 3: 101 Âµs per loop

@BPL solution:
%timeit f1(gibberish)
10000 loops, best of 3: 55.1 Âµs per loop
%timeit f2(gibberish)
10000 loops, best of 3: 31 Âµs per loop
</code></pre>

<h1>Test cases.</h1>

<pre><code>s1 = 'leetcode'
s2 = 'loveleetcode'

&gt;&gt;&gt; first_unique(s1)
0

&gt;&gt;&gt; first_unique(s2)
2
</code></pre>

python