@Sagar: yours is right. but u didn't specify the extra work required
to get the first character non repeating. See the last line of your
solution.
@Varun: I think we can do this in "single traversal" without bit
vectors x,y but just an array[26], taking chars to be 26.
heres how-
take a variable count =0; arr[26] = {0};
traverse the string
for each character,
for(i=0;i<str.length;i++)
{
if(arr[str[i]])
arr[str[i]] = -1;
else
arr[str[i]] = (++count);
}
set min = str.length;
index =0;
for(i=0;i<26;i++)
{
if(arr[i] && arr[i]!=-1)
if(min > arr[i])
{
min = arr[i];
index = i;
}
}
now print i as %c, its the answer.
On Jul 18, 10:03 pm, sagar pareek <sagarpar...@gmail.com> wrote:
> @dumanshu
> first read my soution just above yours :)
>
>
>
>
>
> On Mon, Jul 18, 2011 at 10:21 PM, Dumanshu <duman...@gmail.com> 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 <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.
>
> --
> **Regards
> SAGAR PAREEK
> COMPUTER SCIENCE AND ENGINEERING
> NIT ALLAHABAD- Hide quoted text -
>
> - Show quoted text -
--
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.
