Write a Python function to find the first non-repeating character in a string.

To find the first non-repeating character, the most efficient approach is a two-pass strategy using a hash map (dictionary) to store character frequencies.

Mechanics and Why

The solution involves two distinct passes over the input string.

First Pass (Frequency Count): Iterate through the string once to build a frequency map (e.g., a Python dictionary or collections.Counter). For each character encountered, increment its count in the map. This pass takes O(N) time, where N is the length of the string.

Second Pass (Find First Unique): Iterate through the string again, maintaining the original character order. For each character, check its count in the frequency map. The first character encountered with a count of 1 is the answer. If the loop completes without finding such a character, it means no non-repeating character exists. This pass also takes O(N) time.

A single pass is insufficient because you cannot definitively know if a character is non-repeating until you've scanned the entire string. A character encountered early might repeat later.

Example Implementation

from collections import Counter
def first_non_repeating(s: str) -> str | None:
    if not s:
        return None # Handle empty string
    
    # First pass: Count character frequencies
    counts = Counter(s)
    
    # Second pass: Find the first character with a count of 1
    for char in s:
        if counts[char] == 1:
            return char
            
    return None # No non-repeating character found

Complexity Analysis

* Time Complexity: O(N), where N is the length of the string. This is because we iterate over the string twice. * Space Complexity: O(K), where K is the number of unique characters in the string. In the worst case (all characters are unique), K can be up to N. For ASCII characters, K is at most 256. This space is used to store the frequency map.

Considerations and Best Practices

* Edge Cases: The function should gracefully handle an empty string (returning None) and strings where all characters repeat (also returning None). * Case Sensitivity: Clarify with the interviewer if 'A' and 'a' should be treated as the same or different characters. The provided solution is case-sensitive. * Character Set: The approach works for both ASCII and Unicode characters, as Python dictionaries handle various character types. * Pythonic Approach: collections.Counter is highly recommended for its conciseness and efficiency in counting frequencies. For older Python versions (pre-3.7) where standard dictionaries didn't guarantee insertion order, collections.OrderedDict could be used for the frequency map to ensure the "first" non-repeating character is correctly identified, though modern Python dicts preserve insertion order.

In the interview, also mention…

Always clarify assumptions: what should be returned for an empty string or if no non-repeating character exists? Discuss case sensitivity and the expected character set.