First non repeating character in a stream | Leetcode

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 :)
CODE LINK: gist.github.com/SuryaPratapK/...

[@snehabaser3155]

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

[@bablushaw6856]

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

[@mukulnayak4337]

Its TC is O(N) as we have to traverse the string for once.

[@shishirkakhandki9230]

Thank you so much! Great explanation. Subscribed!

[@spetsnaz_2]

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

[@techdose4u]

List is queue only sir :P

[@spetsnaz_2]

@@techdose4u yeap. I was just sharing my view 😂

[@duraivelp879]

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 ?

[@duraivelperumal1737]

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

[@kanishkumar6176]

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

[@techdose4u]

That's the Library. Dequeue for List and Hashmap for Hash :)

[@anmolgangwal6508]

@@techdose4u no he is saying to use queue, we can maintain order in queue, we can check front of the queue if its repeated pop it and check for other ,otherwise this is the first non repeating character, maximum size of the queue will always be 26

[@karansagar7870]

great explanation but code is slightly different in link

[@amitavamozumder73]

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.

[@amitavamozumder73]

@@farazahmad9734 ooh, that's o(n), didn't know that.

[@mks7846]

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

[@techdose4u]

Solve all the questions of ''Must do questions topic-wise'' from geeksforgeeks. This should give a very good understanding on most algorithm types.

[@bourne0075]

@@techdose4u Yes, even I'm doing that, and it's a great list and covers almost all the important questions.

[@abhinavshukla5164]

@@bourne0075 where is that list can u give me??

[@VishnuVardhan-br4yp]

Please taken questions from playlists of geeksforgeeks arrays &strings questions

[@techdose4u]

I am trying to cover every topic but each one can be done stepwise :)

[@sarcasmtube69]

nice explanation..

[@jamwithharsh]

What platform do you use to make these videos?

[@ayushgarg5929]

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

[@little-by-little-one-trave1770]

The above solution is useful when interviewer asks each query should have exactly o(1) time complexity

[@snehabaser3155]

Best explaination!

[@techdose4u]

Thanks

[@yashgoswami5374]

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?

[@techdose4u]

Solution is correct but it is good only when alphabet size is low. In this case Time = alphabetSize * StreamLength. In the video, time is just StreamLength. If alphabet size is let's say 256 and stringLength = 10^5 then NlogN = 16N but your algo will take 256N. This is way larger than NlogN. I hope you got the point.

[@ashutoshtiwari4719]

Thank You !!

[@techdose4u]

Welcome

[@animeshrajput8638]

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

[@tanveerasif5978]

How will you maintain the order in map ?

[@southern-sunshine]

@@tanveerasif5978 If java you can use LinkedHashMap

[@vinayak186f3]

@@tanveerasif5978 unordered map

[@Pritamdas-bg7fp]

Thanks sir

[@techdose4u]

Welcome :)

[@amanverma9829]

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....

[@techdose4u]

I tend to use DLL by default. You can use SLL if it does the job

[@shishirkakhandki9230]

because while deleting we will have to link previous node with the next node of current node (node to be deleted). Hence we will need to maintain previous node addresses for each node. In DLL we can easily do this as we are already maintaining previous node address in current node. Hence DLL.

[@harshpatel1385]

Amazing work

[@techdose4u]

Do you find this question very simple? Will create a voting for this now. Let's see how our community feels.

[@spetsnaz_2]

@@techdose4u This problem is not simple if we have to do operation in O(1) time

[@Yash-uk8ib]

@@spetsnaz_2 yup

[@techdose4u]

Correct :)

[@harshpatel1385]

@@spetsnaz_2 yes

[@sumhung5942]

But that's assuming you even know the true values of the variables but each failed attempt will just force you to rubix cube it. Or else you reset. Like playing with an rubix cube.

[@sakthim7160]

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.

[@techdose4u]

The second list (or array) is to avoid traversing to find the first non-repeating for each character query. We are just returning head value which ensures O(1) for each query. A DeQueue can be used for this purpose.

[@sakthim7160]

@@techdose4u this approach also will take O(1) for each query and it will allow you to don't keep track of element in a separate list. First time traverse will give you the count of each character and second time traverse for finding the count is equal to one. Time complexity of the code: O(n) Space Complexity: O(26)

[@sakthim7160]

Please note we are traversing the string only two time, not the array. Using the character ascii value I will find out the index of it in my count array in O(1) time.

[@himanshudhyani6076]

For input string =ba Your approach will give ans a. But ans should be b.

[@sakthim7160]

@@himanshudhyani6076my code will give b only. Understand the logic and speak.

[@nagavijaykumarprathi8531]

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(); vectorfreq(26,0); queueque; freq[A[0]-'a']++; que.push(A[0]); res = A[0]; for(int i=1; i

[@Yash-uk8ib]

can it be done without list? i believe only hashing is sufficient.

[@techdose4u]

Actually you will need a Dequeue in place of list :)

[@sakthim7160]

Yes of course hashing is enough and no need for second list.

[@techdose4u]

Actually you need 2nd list and hashing is not enough.

[@sakthim7160]

@@techdose4u hashing only enough, and no need for second list.

[@Yash-uk8ib]

@@techdose4u plzz check this out in c only Hashing is used, if it fails on some testcases plzz reply back #include #include int main() { char s[20],hash[128]={0},f=0; scanf("%s",s); for(int i=0;s[i]!='\0';i++) hash[s[i]]++; for(int i=0;s[i]!='\0';i++) { if(hash[s[i]]==1) { f=1; printf("%c",s[i]); break; } } if(!f) printf("-1"); }

[@shivaycodinghub8967]

On gfg this code is not working for test case in which stream is "hrqcvsvszpsjammdrw" for this the answer is "hhhhhhhhhhhhhhhhhh" but the wrong answer is coming

[@poojasharma9569]

You've just copied the code from Geeksforgeeks and provided it as a link. You should've coded it yourself for us to understand better.

[@premiereprobeginner8975]

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

[@techdose4u]

Nice :)

[@harigovind11]

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 :(

[@sarcasmtube69]

damn...maybe u could hv tried queue...but that's strange m

[@harigovind11]

@@sarcasmtube69 Yeah I think he was looking for the LinkedHashMap based solution

[@pursuitofcat]

''' Implementation in Python for the exact approach described in the video ''' class DNode: def __init__(self, value=None): self.value = value self.next = None self.prev = None class DLinkedList: def __init__(self): self.head = DNode() self.tail = DNode() self.head.next = self.tail self.tail.prev = self.head def push(self, node): node.prev = self.tail.prev node.prev.next = node self.tail.prev = node node.next = self.tail def remove(self, node): node.prev.next = node.next node.next.prev = node.prev class Solution: def firstUniqChar(self, s: str) -> int: existing = {} repititions = defaultdict(bool) dl = DLinkedList() for i, char in enumerate(s): h = ord(char) - ord("a") if h not in existing: node = DNode(i) existing[h] = node dl.push(node) elif not repititions[h]: repititions[h] = True node = existing[h] dl.remove(node) return dl.head.next.value if dl.head.next.value is not None else -1 s = Solution() assert s.firstUniqChar("aabbscdd") == 4

[@chodingninjas7415]

do some hard questions man

[@harshpatel1385]

I am intermediate bro

[@techdose4u]

:P Will do it. I had to complete the topic which I had picked on stack & queue. I am making topic wise video. Stack & queue are simple.

[@Pritamdas-bg7fp]

@@techdose4u sir make video for begginer level

[@techdose4u]

Well I am just picking a topic and making videos to cover that topic. In that way, you can find sufficient videos on different topic to learn from.

[@yashsrivastava677]

What a terribly complex video..Bhai..tu ghar jaa

[@techdose4u]

😂 I am trying to improve. Thanks for your feedback