First Unique Character in a String - Leetcode 387 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/first-u...
0:00 - Read the problem
0:18 - Drawing Explanation
2:48 - Coding Explanation
leetcode 387
#neetcode #leetcode #python

[@spontaneoussam2]

Nice, great to see I'm not the only one doing two passes on the input string 😂

[@divyanshsharma673]

It can't be done in single pass anyway

[@TheElementFive]

We can use a deque to keep track of letters for which we haven’t found duplicates for as we iterate, and a hash set to keep track of letters that have already been determined to have duplicates. At the end we can return the first unique element from the deque in constant time. This allows for a one pass solution at the slight expense of a second data structure.

[@josefjelinek]

Hashmap will be much slower and bigger than an array of 26 integers which is all you need in this case... not all O(N) are the same in production.

[@harrisonhutton]

neato!!

[@razataggarwal7365]

I did it in O(N+26) You just need to 1. store char,freq,firstIndex info. 2. populate it using string 3. traverse every 26 char and get min firstIndex with freq=1. Still, in leetCode it runs slower than Two pass solution.

[@Munchen888]

Allilya! 😂 Also you can use methods od str: index , rindex

[@DeathSugar]

The more efficient way is to save index in first cycle and if its non-zero then max it and filter out in the second cycle and look for the minimal index.

[@no_mnom]

you mean just have it be an index instead of a count and if the value already existed then you set it to -1. In the end you just return the smallest value that's 0 or larger. That would be roughly the same would it not?

[@DeathSugar]

​@@no_mnom kinda, yes. you have an array of 26 elements filled with something (-1 for example). first cycle - we collect "frequencies". pick a character (c) and it's current index (n) and convert it to array index if we never met it, we will have -1 at index so we put current index n if we met it ,then we just put some out of bound value > 26, i used int32 max. second cycle - we skip zeroes (which we never visited) and out of bound values (which we visited twice ot more). the rest as visited exactly once and we select the minimal value which is the minimal index which is the first non-repeating and return it our answer.

[@tango2olo]

Two pass soln is easy. Replacing the string with a stream shall force us to use one pass.

[@venil82]

theres more efficient solution with using (and filling) the set as you iterate thru the string technically its better than O(n)

[@WhosShamouz]

That was a neet problem 🤞

[@ShivKatira]

why are you using defaultdict instead of Counter? any specific reason ?

[@drewstake3881]

Both defaultdict(int) and Counter are appropriate for this task, and the choice between them does not significantly affect the logic or performance of the solution for finding the first non-repeating character in a string. It's more about his preference

[@Yougottacryforthis]

counter is what you should use its exactly the usecase

[@xavierwayne2031]

Single-pass solution for those who wonder. Do the pass and build the hash map. Key is the character, value is a double-linked list item, ie a struct with two pointers: prev & next. Outside the loop also define two separate pointers to the first and last linked list items. On each character check if it’s already in the map. If not, add it. As the value put the double-link list item in the end of the list: set prev = last, next = null. Update last, too. If the character is already in the map, “delete” the corresponding value: set prev.next = next and next.prev = prev. This deletion uses both hash map and linked list pointers. Then null the value of the deleted char, to avoid deleting it twice, set prev = next = null. When the pass is over, the first would point to the correct char or null

[@Kam_717]

c++ code : class Solution { public: int firstUniqChar(string s) { vector v(2e5,0); for(long long i= 0 ; i < s.size() ; i++){ char ch = s[i]; v[(int)(ch - '0') - 1] = v[(int)(ch - '0') - 1] + 1; } for(int i = 0 ; i< s.size() ; i++ ){ char ch = s[i]; int index= i ; if(v[(int)(ch - '0') - 1 ] == 1){ return index; } else{ continue; } } return -1; } };

[@chrischika7026]

My code class Solution: def firstUniqChar(self, s: str) -> int: count = Counter(s) return next((i for i in range(len(s)) if count[s[i]] == 1),-1)

[@mahdirostami7034]

When solving algorithm problems the worst thing you can do is using buit-in functionality. However considering how slow Python is, if the count method for strings is implemented in C (I'm not sure if it is) it might even be faster than the efficient algorithm implemented in python (Knowing how slow Python for loops are)

[@kizhissery]

can you share leetcode userid

[@user-ph5iz4qb3t]

I have faster solution O(N*K) instead O(2*N). itnot big difference but I think idea is good python: class Solution: def firstUniqChar(self, s: str) -> int: freq_dict = {} for index, char in enumerate(s): freq_dict[char] = -1 if char in freq_dict else index for char, index in freq_dict.items(): if index != -1: return index return -1

[@chase-warwick]

This doesn't necessarily work because it assumes that your dict will be ordered and that isn't guranteed. The order that you put items into the hashmap will not necessarily be the order that they are returned via the items function. Since we want the first unique character (and not just any unique character).

[@bewinmarshel]

I am new to coding but can anyone please expain why my time limit exceeded for this solution class Solution: def firstUniqChar(self, s: str) -> int: for i in range(0,len(s)): count = 0 for j in range(0,len(s)): if s[i] == s[j]: count += 1 if count == 1: return i return -1

[@tharunr42]

I hope you would have got the time limit exceeded for the testcase - 25 in Leetcode, which has a input string length of 31713 characters, since your code runs in O(n^2) time, for the input 31713, the loop runs 1.005714369 * 10^9 which is more than the threshold of Leetcode's time limit which is < 10^9(Basically one second). That's why you get time limit exceeded... Hope it helps

[@bewinmarshel]

​@@tharunr42 Yes brother it helps ,thanks for letting me know. And whether changing my approach is only way to solve this problem or is there anyother way to make it work by using lesser time. I am not getting any other way

[@tharunr42]

@@bewinmarshel You have to go with the optimized solution to solve this problem, that is to reduce the time complexity from O(n ^2) to O(n) or O(log n), whichever possible, as the given input constraints clearly state the size will be upto

[@bewinmarshel]

@@tharunr42 yes bro now it's working .Thank you

[@varunsai9736]

First comment and view

[@justcurious1940]

I don't know Python but I know C : int unique_character(char *string){ int i = 0; while(string[i] != '\0'){ bool unique = true; int j = 0; while(string[j] != '\0'){ if(i != j && string[i] == string[j]){ unique = false; break; } ++j; } if(unique) return i; ++i; } return -1; } Sorry If u are not interested at all.

[@DAIS_Shujaathullakhan]

Someone share 1 pass solution

[@cm5754]

str = 'sdfdsdxxfa' queue = [] for pos in range(len(str)) : char = str[pos] data = [char, 1, pos] found = 0 for i in range(len(queue)) : if queue[i][0] == char : found = 1 queue[i][1] = queue[i][1] + 1 if found == 0 : queue.append(data) pos = -1 for i in range(len(queue)) : if queue[i][1] == 1 and pos == -1 : pos = i print(pos)

[@cm5754]

It would be easier to make queue a linked list but this is Python. Since the length of queue is bounded the overall code is O(N), where N is the length of the string. The final loop is O(1).