Cfrgtkky

IMHO looping twice over the input string is not acceptable for multiple reasons

• the string is of unknown size


• you invalidate your code for generators

While this might not be necessary for your project you should learn to think like that. So a single pass algorithm should collect all necessary data to answer the question (e. g. the letter in original case).

import sys

assert sys.version_info >= (3, 6)



def non_repeat(s):

    repeated = set()

    candidates = dict()

    for original_case in s:

        lower_case = original_case.lower()

        if lower_case not in repeated:

            if lower_case not in candidates:

                candidates[lower_case] = original_case

            else:

                repeated.add(lower_case)

                del candidates[lower_case]



    if candidates:

        return next(iter(candidates.values()))

    else:

        return ''

This code makes use of the insertion order of a dict which is already implemented in 3.6 and guaranteed in 3.7.

Edit: generator example

Say you want to check a big file that does not fit into memory (for brevity I assume a line fits into memory). Yor write a little character generator and run your algorithm on the generator.

def char_gen(f):

    for line in f:

        for c in line.strip():

            yield c



with open('bigfile.txt') as f:

    print(non_repeat(char_gen(f)))

also you might use the algorithm on a generator expression

print(non_repeat(c for c in "aabbcd" if c != 'c'))

I would separate counting from keeping the initial positions. This would allow to use collections.defaultdict for counting and simplify the code and contribute to readability:

from collections import defaultdict





def non_repeat(input_string):

    counts = defaultdict(int)

    positions = {}



    for position, letter in enumerate(input_string.lower()):

        counts[letter] += 1

        positions[letter] = position



    for letter in input_string.lower():

        if counts[letter] == 1:

            return input_string[positions[letter]]



    return ''

Going further from alecxe's answer:

• you could use the Counter collections instead of performing the counting yourself - I didn't see that this was avoided on purpose.


• you can ensure lower is called only once

You'd get something like:

from collections import Counter



def non_repeat(input_string):

    lower = input_string.lower()

    count = Counter(lower)

    for c, l in zip(input_string, lower):

        if count[l] == 1:

            return c

    return ''

or, for a Counter-less solution:

def non_repeat(input_string):

    lower = input_string.lower()

    count = defaultdict(int)

    for c in lower:

        count[c] += 1

    for c, l in zip(input_string, lower):

        if count[l] == 1:

            return c

    return ''

Also, here's a quick test suite I wrote:

tests = [

    ('', ''),

    ('AA', ''),

    ('AAABBB', ''),

    ('AAABBBc', 'c'),

    ('azerty', 'a'),

    ('aazzeerty', 'r'),

    ('azerAZERty', 't'),

]



for inp, out in tests:

    assert non_repeat(inp) == out

A version which doesn't use any imports, works on Py2.7+ and relies almost solely on set operations to achieve a single O(len(s)) pass + constant time:

def non_repeat(s):

    LEN_CHAR_SET_LOWERED = XXX  # length of your char set adjusted for .lower()

    seen_order =   # Store the order for figuring out which came first

    seen_set = set()  # Store whether we've seen the character

    dupe_set = set()  # Store whether we've seen it more than once



    # Scan the string

    for ch in s:

        chl = ch.lower()  # lowered character for seen/dupe sets

        if chl not in seen_set:

            seen_order.append(ch)  # This uses the non-lowered version to preserve case

            seen_set.add(chl)

        else:

            dupe_set.add(chl)

            if len(dupe_set) == LEN_CHAR_SET_LOWERED:  # Set len is O(1)

                return ''  # If dupe set contains all possible characters, exit early



    # Find uniques

    unique_set = seen_set - dupe_set



    # Find the first one, if any

    if unique_set:

        for ch in seen_order:

            if ch.lower() in unique_set:

                return ch

    return ''

Some notes on speed:

• O(len(s)) average case, O(1) best case (see early exit) - to build the list/sets - set membership, additions and list appends are all average O(1) operations, worst case O(len(set/list))*




• O(1) - Set difference on average, worst case O(len(set))*




• O(len(list))* for the final check

*O(len(list)) and O(len(set)) both have upper bounds of LEN_CHAR_SET_LOWERED, which means they end up constant time, O(1), as the string grows

This is also interesting because of the early exit: If your string contains all characters duplicated, it will only scan until it has seen every character at least twice and then exit, knowing there will be no unique characters. An alphanumeric string could exit after scanning as few as 72 characters, regardless of the actual length.