# The Lone Traveler

> One character stands apart from the crowd.

Canonical URL: <https://datadriven.io/problems/the_lone_traveler>

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given a string, return the first character (leftmost) that appears exactly once in the string. If all characters repeat, return an empty string.

## Worked solution and explanation

### Why this problem exists in real interviews

This is a variant of the first-unique-character problem that tests **dictionary-based frequency counting** and maintaining original string order during lookup. It is a warm-up that reveals whether candidates default to efficient O(n) approaches or resort to O(n^2) nested loops.

---

### Break down the requirements

#### Step 1: Build a frequency map

Count occurrences of each character in a dictionary with a single pass.

#### Step 2: Walk the original string

Check each character against the frequency map. Return the first one with count 1.

#### Step 3: Return empty string if none found

If every character repeats, the function returns an empty string as specified.

---

### The solution

**Frequency map with ordered re-scan**

```python
def first_non_repeating(s):
    freq = {}
    for ch in s:
        if ch in freq:
            freq[ch] += 1
        else:
            freq[ch] = 1
    for ch in s:
        if freq[ch] == 1:
            return ch
    return '' 
```

> **Time and Space Complexity**
>
> **Time:** O(n) with two linear passes over the string.
> 
> **Space:** O(k) where k is the number of distinct characters.

> **Interviewers Watch For**
>
> Do you instinctively reach for a dict-based approach? Candidates who write `s.count(ch)` inside a loop produce O(n^2) and signal they are not thinking about complexity.

> **Common Pitfall**
>
> Confusing 'non-repeating' with 'unique in the list'. A character that appears once is non-repeating; a character that appears twice is repeating even if it appears consecutively.

---

## Common follow-up questions

- What if the input were a stream and you could not re-scan? _(Tests streaming algorithms with ordered sets or linked list + hash map combos.)_
- How would you adapt this for case-insensitive matching? _(Tests normalization: `.lower()` before counting, but return original case.)_
- What if you needed the index instead of the character? _(Tests minor modification to return position on second pass.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_lone_traveler)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.