@@danzielcempron2589 Queue for characters seen in order. Set for unique characters seen so far Iterate over the input string and add it to unique characters and queue. If we find the same character in Set, It is a duplicate so delete it from Queue. The Queue at the end will have the first unique element of the string
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.
I did this iterating on the Hashmap instead of the string again, since best case the hashmap is smaller, worst case is the same size. In the map I use the char as key and as value an array with the count and last seen index.
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.
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)
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
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
@@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
@@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
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
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.
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.
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?
@@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.
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 Nah you wrong, its going to work, you know why, cause after setting every value that appeared more than once to -1, you will have something like this {'l': -1, 'o': -1, 'v': 2, 'e': -1, 't': 7, 'c': 8, 'd': 10} if loveleetcode is the input right ??, now when you traverse the hash map the second time, you will be returning the index of the first positive value which is v, with the value of 2, cause we actually want to return immediately we encounter the first positive value, cause they might be more than one positive value, so the solution is very very efficient, Nice Work Brother 🏆.
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
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)
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).
Nice, great to see I'm not the only one doing two passes on the input string 😂
It can't be done in single pass anyway
@@divyanshsharma673 I don't know until I see someone solving it in one pass
@@divyanshsharma673 Apparently, It can be done in single pass.
@@nandkarthik How?
@@danzielcempron2589
Queue for characters seen in order.
Set for unique characters seen so far
Iterate over the input string and add it to unique characters and queue. If we find the same character in Set, It is a duplicate so delete it from Queue.
The Queue at the end will have the first unique element of the string
theres more efficient solution with using (and filling) the set as you iterate thru the string
technically its better than O(n)
Allilya! 😂 Also you can use methods od str: index , rindex
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.
I did this iterating on the Hashmap instead of the string again, since best case the hashmap is smaller, worst case is the same size. In the map I use the char as key and as value an array with the count and last seen index.
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.
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.
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;
}
};
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)
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)
Two pass soln is easy. Replacing the string with a stream shall force us to use one pass.
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
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
@@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
@@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
@@tharunr42 yes bro now it's working .Thank you
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
neato!!
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.
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.
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?
@@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.
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 Nah you wrong, its going to work, you know why, cause after setting every value that appeared more than once to -1, you will have something like this {'l': -1, 'o': -1, 'v': 2, 'e': -1, 't': 7, 'c': 8, 'd': 10} if loveleetcode is the input right ??,
now when you traverse the hash map the second time, you will be returning the index of the first positive value which is v, with the value of 2, cause we actually want to return immediately we encounter the first positive value, cause they might be more than one positive value, so the solution is very very efficient, Nice Work Brother 🏆.
That was a neet problem 🤞
can you share leetcode userid
why are you using defaultdict instead of Counter? any specific reason ?
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
counter is what you should use its exactly the usecase
Someone share 1 pass solution
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)
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).
First comment and view