Find first non-repeating character in a string by doing only one traversal of it

Given a string, find first non-repeating character in it by doing only one traversal of it.

 

For example,


Input:
string is ABCDBAGHC

Output:
The first non-repeating character in the string is D

 

 
A simple solution would be to store count of each character in a map or an array by traversing it once. Then we traverse the string once more to find the first character having its count as 1. The time complexity of this solution is O(n) and auxiliary space used is O(n). The problem in this solution is that we are traversing the string twice and it violates the program constraints.

 
We can solve this problem in single traversal of the string. The idea is to use a map to store each distinct character count and the index of its first or last occurrence in the string. Finally, we traverse the map and find character having count 1 and minimum index in the string. Note that in this solution we are doing one traversal of the string and one traversal of the map. Since, the size of the map is equal to alphabet size in worst-case (which is a constant), it can be ignored.

 
C++ implementation –
 

Download   Run Code

Output:

The first non-repeating character in the string is D

 
The time complexity of this solution is O(n) and auxiliary space used by the program is O(1).

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Timmy Jose
Guest
Timmy Jose

Why not simply use a Set and keep another variable storing the last inserted character. When we encounter a repetition, then the variable will be the answer.

Aditya
Guest
Aditya

Won’t work.

Hitesh
Guest
Hitesh

We can use LinkedHashSet to store character newly found
If repeat, remove from LinkedHashSet
Finally check if set is not empty (not all repeated chars)
then return first element from set.

Hitesh
Guest
Hitesh

We should rather be using a LinkedHashMap of Char to isRepeat
If char already present, store
else store
Then iterate map to find first entry with

Nishant
Guest
Nishant

arandomguy
Guest
arandomguy

Wrong