First non repeating character in a stream | Leetcode #387

This video explains a very frequently asked programming interview question which is to find the first non-repeating character in a stream of characters. This is an online algorithm which means we need to output answer for each character input. This video explains the problem elegantly using example which takes only O(1) time for each query and so if we have a string of size N then total is just O(N). This is the most efficient solution for this problem. As usual, the CODE LINK is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[bablushaw]

Beautiful logic. I was shocked when realized this problem is solved in TC O(1) only.

[kanishkumar]

We can also use queue and hash map
(Queue can slightly improve runtime performance)

[snehabaser]

Could you please explain approach having time complexity O(26*N) and space complexity O(26).

[ayushgarg]

Why there is a need of extra queue... just use another pointer that will always point to first non repeating character and if it is not then increase the pointer until we find the new first non-repeating character

[karansagar]

great explanation but code is slightly different in link

[spetsnaz_]

Amazing Way to solve this problem. Never thought of such intuitive solution. I solved this problem using Queue

[amitavamozumder]

if we're using JS we can use new Map(), then the keys will be added in insertion order, so we don't need anything else.

[sakthim]

I don't know why are you using two arrays. I solved this problem yesterday using single integer array of size 26. The elements in array initially will be zero. Then we have to traverse the string and we know that all are small alphabet so the ascii value will range from 97 to 122 so we can get the index of that character by subtracting 97 from it's ascii value. For each character in the string from left to right I will take ascii and I will increment the count of that character in my array.
Now we have to again traverse the string from left to right and check the count of each character. When ever you find count is equal to one stop traverse and print that character or else return -1.

[VishnuVardhan-bryp]

Please taken questions from playlists of geeksforgeeks arrays &strings questions

[mks]

please provide me a list of questions for each topic you said to prepare for interview...

[animeshrajput]

I think we can do this question by just using unordered map. I tried it in leetcode and it worked

[harigovind]

I was asked this question by Oracle OCI and gave this exact solution with working code and ran against example testcases. But interviewer rejected telling it's a complicated solution :(

[premiereprobeginner]

you teach really well, I am 100% sure you are either an iitian or an nitian .
By the way thanks for the beautiful explanation, i was able to write the code myself just by understanding the strategy

[nagavijaykumarprathi]

my queue based solution
string FirstNonRepeating(string A){
// Code here
// step 1 : find freq
// step 2 : if freq == 1, (it is not repeating char) push into queue
// step 3 : check the first non repeating char in que, if the pee ele is not first non repeating, pop from que
// step 3 : if queue is empty (we dont find first non repeating char) else peak_ele is first not repeating char
string res = "";
int n = A.size();

vector<int>freq(26, 0);
queue<char>que;


freq[A[0]-'a']++;
que.push(A[0]);
res = A[0];

for(int i=1; i<n; i++){
freq[A[i]-'a']++;

if(freq[A[i]-'a']==1){
que.push(A[i]);
}

while(!que.empty()){
char peek_ele = que.front();
if(freq[peek_ele-'a']==1){
break;
}else{
que.pop();
}
}

if(que.empty()){
res += "#";
}else{
res += que.front();
}

}

return res;
}

};

[duraivelperumal]

Why we use doubly linked list here, is there any special use case for that ...? Little bit confused on this point only..

[yashgoswami]

can't we do the following?
if we take array of size 26
for each a[ i ] we will have 3 options 0, 1, 2
initially all will be 0
0 stands for non visited or not came till now
1 stands for came only one time
2 stands that, character is repeated


so, whenever is the first 1 it will be our ans.


if array is taking more time then you can suggest batter DS.(may be hashmap)


and if this solution is not that good then tell me why?

[duraivelp]

Why we use extra boolean array since we already have the address array so we can just check if the data is null or not in the address array and then insert the new node ? Am i missing anything here ?

[shishirkakhandki]

Thank you so much! Great explanation. Subscribed!

[amanverma]

why we need doubly linked list we can do the the same by singly linked list.
we don't need to traverse back then why we are using DLL.
please have a comment....

[jamwithharsh]

What platform do you use to make these videos?