First non-repeating letter

Question

The problem: find and return the first nonrepeating character in a string, if the string does not have a nonrepeating character return an empty string. For purposes of finding the nonrepeating character it's case insensitive so 't' and 'T' appearing in the string would imply that that 't' and 'T' are not candidates for a nonrepeating character. When you return the character you must return it as its original case.

My Solution:

def non_repeat(_str):
    counts = {}
    for pos, letter in enumerate(_str.lower()):
        if letter not in counts:
                counts[letter] = (0, pos)
        incr_val = counts[letter][0] + 1
        counts[letter] = (incr_val, pos)
    for letter in _str.lower():
        if counts[letter][0] == 1:
            return _str[counts[letter][1]]
    return ''

How can I improve the readability of my solution? In particular, I don't like:

• counts[letter][0] because the 0 index is a bit ambiguous.
• calculating the incremented value as another line, incr_val; it'd be nice to do the incrementing and updating of the dict in one line.

Anything else you could make more readable? I should add that I'm aware of collections.​Counter; for this solution I'd like to avoid using it.

Answer 1

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'))

Answer 2

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 ''

Answer 3

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

Answer 4

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.