DSA problem

First Non-Repeating Character

MediumStringsPattern: Frequency CountbeginnerFreeAmazonGoogleMicrosoft

Given a string s, find the first character that does not repeat. If all characters repeat, return _.

Build a frequency map in one pass. Then make a second pass through the string (not the map - order matters) and return the first character with a count of 1. The two-pass approach is O(n) time and O(1) space since the alphabet is fixed. Iterating over the string for the second pass is crucial because maps do not guarantee insertion order in all languages. This problem is asked frequently at Amazon, Google, and Microsoft, and is the foundation for the first-unique-character-in-a-stream problem, which uses a queue and a hash set - a common component for real-time deduplication.

Examples

Example 1

Input: s = "aabbcdd"

Output: c

Explanation: a, b, and d each appear twice; c is the first character with a count of 1.

Example 2

Input: s = "aabb"

Output: _

Explanation: Every character repeats, so there is no non-repeating character.

Constraints

1 <= s.length <= 10^5
String contains only lowercase English letters

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

stringhash-tablecounting

Browse all DSA problems