Quick Overview

Return the first character whose total frequency is one, preserving input order and defining the result when every character repeats.

Return the First Non-Repeating Character

Company: Goldman Sachs

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given a string `s`, return its first character that occurs exactly once in the entire string. “First” refers to the character's position in the original string. ### Input - `s`: an ASCII string. ### Output Return the first non-repeating character as a one-character string. For this practice version, return an empty string if no such character exists. ### Constraints and Edge Cases - `0 <= s.length <= 100000`. - Character comparison is case-sensitive, and spaces or punctuation count as ordinary characters. - Return the character itself, not its index. - A character is non-repeating only if its total frequency is one, even if its occurrences are far apart. - An empty input returns an empty string. ### Example 1 ```text s = "swiss" output = "w" ``` The first character, `s`, repeats. Both `w` and `i` occur once, and `w` appears first. ### Example 2 ```text s = "aabb" output = "" ``` Every character repeats.

Overview: Return the first character whose total frequency is one, preserving input order and defining the result when every character repeats.

Given a string `s`, return its first character that occurs exactly once in the entire string. “First” refers to the character's position in the original string. ### Input - `s`: an ASCII string. ### Output Return the first non-repeating character as a one-character string. For this practice version, return an empty string if no such character exists. ### Constraints and Edge Cases - `0 <= s.length <= 100000`. - Character comparison is case-sensitive, and spaces or punctuation count as ordinary characters. - Return the character itself, not its index. - A character is non-repeating only if its total frequency is one, even if its occurrences are far apart. - An empty input returns an empty string. ### Example 1 ```text s = "swiss" output = "w" ``` The first character, `s`, repeats. Both `w` and `i` occur once, and `w` appears first. ### Example 2 ```text s = "aabb" output = "" ``` Every character repeats.

Constraints

  • s is an ASCII string with character codes 0 through 127.
  • 0 <= s.length <= 100000.
  • Comparison is case-sensitive. Whitespace, punctuation and ASCII control characters count as ordinary characters.
  • Return the first globally unique character in original order, as a one-character string; return an empty string if none exists.

Examples

Input: ('swiss',)

Expected Output: 'w'

Explanation: Published sample 1: s repeats; w is the earliest globally unique character.

Input: ('aabb',)

Expected Output: ''

Explanation: Published sample 2: every character repeats.

Loading coding console...

Show the approach

Approach

Count the occurrences of each ASCII code using an array of 128 counters. Complete this pass before selecting an answer: a character that has appeared only once so far may repeat later.

Scan the original string again from left to right. Return the first character whose final count is one. If that scan finds no such character, return the empty string.

After the first pass, each counter is the total frequency of its character in the entire input. Therefore the second pass accepts exactly globally unique characters. Its original left-to-right order makes the first accepted character the required answer. If no counter encountered in the string equals one, no valid answer exists. Empty input follows the same rule. Uppercase and lowercase letters, whitespace, punctuation, NUL and DEL have distinct ASCII codes and receive no special filtering or normalization.

The algorithm takes O(n + 128) time and O(128) auxiliary space, which are O(n) time and O(1) space for the fixed ASCII alphabet. Counters never exceed 100000. The C++ by-value string parameter can additionally copy O(n) input storage; the frequency table and scanning state remain constant-sized.

Time complexity:
O(n + 128), or O(n) for the fixed ASCII alphabet.
Space complexity:
O(128) = O(1) auxiliary working space; the C++ by-value string parameter may copy O(n) input storage.