The First Stranger

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
Asked in
Speakeasy

Problem

A short string of single-character status codes arrives in the order records were processed. Return the first code that appears exactly once, or an empty string if every code repeats.

In a crowd, the unique ones stand out first.

Example 1

Input:

s = "swiss"

Output:

"w"

Example 2

Input:

s = "aabbcc"

Output:

""

Worked solution and explanation

What this really is

Beneath the 'first stranger' costume this is a frequency count welded to an order-preserving scan. The catch every mid-level candidate walks into: they try to do it in one pass with a 'seen' set and return the first character they have not seen before. That fails silently. In 'swiss' the very first character 's' has not been seen yet, so the one-pass shortcut hands back 's', even though 's' shows up three times. You cannot decide 'appears exactly once' until you have counted the whole string, which is exactly why the honest solution needs two passes: count everything first, then walk the string in original order and return the first character whose count is one.

The two passes

Step 1: Count every character first

Walk the whole string once and tally how many times each character occurs. You need the totals complete before you can trust any single character, so this pass must finish before you decide anything.

Step 2: Scan in original order

Walk the original string again, in order, and return the first character whose tally is one. Scanning the string (not the dict) is what guarantees you get the leftmost qualifier.

The solution

Count, then scan in order
def first_non_repeated(s: str) -> str:
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    for ch in s:
        if freq[ch] == 1:
            return ch
    return ""
One-pass 'seen' set (wrong)
Iterate once, return the first character not previously seen. On 'swiss' it returns 's' immediately, because 's' is new on the first step. But 's' repeats twice more, so the answer is wrong. The prefix cannot know the future.
Count then scan (correct)
First pass fixes every count; second pass returns 'w', the first character whose total is one. Correct because the decision is made against complete information, in original order.

Common follow-up questions