The Lone Traveler

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L3

Problem

Find the leftmost character that occurs exactly once anywhere in s, a request ID an on-call engineer is checking for a mistyped character, or an empty string when every character repeats. Uppercase and lowercase are different characters.

One character stands apart from the crowd.

Example 1

Input:

s = "leetcode"

Output:

"l"

Example 2

Input:

s = "aabb"

Output:

""

Worked solution and explanation

This is a two-pass counting problem dressed up as a typo hunt. Everyone builds a frequency map; what separates candidates is knowing you cannot call a character unique until you have counted the entire string. The tempting shortcut returns the first character that has not repeated yet, and on 'loveleetcode' that hands back 'l' at index 0, which repeats two letters later. The right answer is 'v', and you only know that after the last character has been tallied.

Why one pass is not enough

Decide while reading
Return a character the moment it has no earlier twin. Works on 'leetcode' by luck, returns 'l' on 'loveleetcode' because the second 'l' has not been read yet.
Count, then decide
Finish the tally first, then rescan s in its original order. Every verdict uses the full-string count, so 'loveleetcode' correctly yields 'v'.

Step 1: Tally every character first

Walk s once and bump a count per character in counts. No answer is possible yet, because any character can reappear at the very end.

Step 2: Rescan s, not the tally

The answer is defined by position in the original string, so the second pass walks s left to right and stops at the first character whose total is 1. That stop is what makes it the leftmost.

Step 3: Fall through to an empty string

If the second loop finishes without returning, every character repeated (or s was empty), so return ''.

Full tally, then an ordered rescan
def first_unique_char(s):
    counts = {}
    for ch in s:
        if ch in counts:
            counts[ch] += 1
        else:
            counts[ch] = 1
    for ch in s:
        if counts[ch] == 1:
            return ch
    return ''

Common follow-up questions