wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> first non repeated character in a string
        
(Message started by: sat90 on Aug 9^th, 2011, 12:50am)

Title: first non repeated character in a string
Post by sat90 on Aug 9^th, 2011, 12:50am

find first non repeated character in a string in o(n) time and 0(1) space...

Title: Re: first non repeated character in a string
Post by srikanth on Aug 9^th, 2011, 7:56am

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.

Title: Re: first non repeated character in a string
Post by towr on Aug 9^th, 2011, 8:58am

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.

Title: Re: first non repeated character in a string
Post by sat90 on Aug 11^th, 2011, 6:42am

@srikanth:

the above code finds sol for non repeated character in alphabetical order

test case: b a
your output: a

expected output:b

Title: Re: first non repeated character in a string
Post by towr on Aug 11^th, 2011, 10:12am

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.

Title: Re: first non repeated character in a string
Post by sat90 on Aug 12^th, 2011, 10:27am

sorry.........got it