Find the first non-repeating character

Summary

Find the first character in a string that appears only once.

Problem statement

Given a string s, find and return the first character that appears exactly once in s. The input is case-sensitive: 'A' and 'a' are different. If no such character exists, return an empty string ''. If s is empty, return ''. Aim for O(n) time using a single or two-pass approach.

Task

Return the first non-repeating character from a string (case-sensitive). If none exists, return an empty string.

Examples

Input format

One string argument: find_first_non_repeating(s)

Output format

Return a single-character string representing the first non-repeating character, or '' if none.

Constraints

0 <= len(s) <= 10^5. Use O(n) time and O(k) additional space where k is alphabet size.

Samples