0(n) time o(1) spcae(Dont be too harsh please I am just using 64 bytes of
extra space)
#include<bitset>
#include<iostream>
#include<queue>
using namespace std;
int main()
{
char answer;
bitset<26> charset;
bitset<26> repeat;
char a[]={'s','a','s','a','b','v','s','a'};
#ifdef TEST
gets(a);
#endif
int i;
for(i=0;a[i]!='\0';i++){
if(charset.test(a[i]-'a')) {
repeat.set(a[i]-'a');
}
charset.set(a[i]-'a');
}
for(int j=0;j<i;j++)
{
if(!repeat.test(a[j]-'a')){
cout<<a[j]<<endl;
return 0;
}
}
cerr<<"No non repeating Character"<<endl;
return 0;
}
On Tue, Jul 19, 2011 at 2:30 AM, Dumanshu <duman...@gmail.com> wrote:
> @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.
>
>
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
