heres my solution with TC O(n) and SC O(26)
input string str
int arr[26] = {0};
traverse the string, character by character and increment the
corresponding counter.
i.e. arr[str[i]]++;
Now traverse the string again and print out the first character
encountered whose arr[str[i]] == 1;
On Jul 18, 9:20 pm, sagar pareek <sagarpar...@gmail.com> wrote:
> 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 <harry.rat...@gmail.com> 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 algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
