@dumanshu
first read my soution just above yours :)
On Mon, Jul 18, 2011 at 10:21 PM, Dumanshu <[email protected]> wrote:
> 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 <[email protected]> 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 <[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.
>
>
--
**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.
