Author |
Topic: first non repeated character in a string (Read 1948 times) |
|
sat90
Newbie
Posts: 7
|
 |
first non repeated character in a string
« on: Aug 9th, 2011, 12:50am » |
 Quote  Modify
|
find first non repeated character in a string in o(n) time and 0(1) space...
|
|
 IP Logged |
|
|
|
srikanth
Newbie
Posts: 1
|
|
Re: first non repeated character in a string
« Reply #1 on: Aug 9th, 2011, 7:56am » |
Quote Modify
|
Code:
char FindFirstNonDuplicate(char *s, int n)
{
char hash[256] = { 0 };
for(int i=0;i<n;i++) hash[s[i]]++;
for(int i=0;i<n;i++) if(hash[s[i]] == 1) return s[i];
return -1
}
|
|
I am not sure if it is O(1) space complicity because of hash.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: first non repeated character in a string
« Reply #2 on: Aug 9th, 2011, 8:58am » |
Quote Modify
|
Yes, that qualifies as constant space, since it's a fixed size.
It wouldn't work for UTF-8 characters though, since those may consist of multiple bytes and then a 256 long hashtable is too small.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sat90
Newbie
Posts: 7
|
|
Re: first non repeated character in a string
« Reply #3 on: Aug 11th, 2011, 6:42am » |
Quote Modify
|
@srikanth:
the above code finds sol for non repeated character in alphabetical order
test case: b a
your output: a
expected output:b
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: first non repeated character in a string
« Reply #4 on: Aug 11th, 2011, 10:12am » |
Quote Modify
|
I think you're misreading his algorithm, it would return b as expected. He runs through the string twice, the second time returning the first character whose count in the hash is 1.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sat90
Newbie
Posts: 7
|
|
Re: first non repeated character in a string
« Reply #5 on: Aug 12th, 2011, 10:27am » |
Quote Modify
|
sorry.........got it
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print