Very good solution :- but space complexity = O(26)
take integer array arr[0-25] and initialise it with 0 by taking it static
logic is that we have only 26 characters so if i want to map character 'a'
with 0th position of arr[] then it can be done as atoi('a')-97.
so whenever we encounter any character say str[i] (where str is array of
given string) then it can be incremented as arr[atoi(str[i])-97]++
so traverse the whole str[] and increment the corresponding values .
At the end those characters which never encounter have values 0 in arr ,
which encounter only once have values 1 and more than once have values>1.
at the end traverse the whole arr[] and find out the corresponding character
as itoa(arr[i]+97) :) :)
But we have to do extra work to find the first character which repeats only
once
On Mon, Jul 18, 2011 at 8:09 PM, hary rathor <[email protected]> wrote:
> can we use bit vector ?
> because by do it we need just 32 bits of one extra variable .
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
