Re: [algogeeks] Re: Long string and the first non-repeating character
@arun yes it is,,
On Tue, Aug 2, 2011 at 2:36 PM, Arun Vishwanathan wrote:
> so can someone please tell me the O(1) space and O(n) time solution to
> this?
> @saurabh :can u explain yr logic?is it an O(1) space solution since u have
> used a 26 element vector?
>
>
>
> On Tue, Jul 19, 2011 at 4:50 AM, saurabh singh wrote:
>
>> 0(n) time o(1) spcae(Dont be too harsh please I am just using 64 bytes of
>> extra space)
>>
>>
>>
>> #include
>> #include
>> #include
>> 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> {
>> if(!repeat.test(a[j]-'a')){
>> cout<> return 0;
>> }
>> }
>> cerr<<"No non repeating Character"<> return 0;
>> }
>>
>> On Tue, Jul 19, 2011 at 2:30 AM, Dumanshu 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>> {
>>> 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 wrote:
>>> > @dumanshu
>>> > first read my soution just above yours :)
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > On Mon, Jul 18, 2011 at 10:21 PM, Dumanshu
>>> 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 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 em
Re: [algogeeks] Re: Long string and the first non-repeating character
so can someone please tell me the O(1) space and O(n) time solution to this?
@saurabh :can u explain yr logic?is it an O(1) space solution since u have
used a 26 element vector?
On Tue, Jul 19, 2011 at 4:50 AM, saurabh singh wrote:
> 0(n) time o(1) spcae(Dont be too harsh please I am just using 64 bytes of
> extra space)
>
>
>
> #include
> #include
> #include
> 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 {
> if(!repeat.test(a[j]-'a')){
> cout< return 0;
> }
> }
> cerr<<"No non repeating Character"< return 0;
> }
>
> On Tue, Jul 19, 2011 at 2:30 AM, Dumanshu 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> {
>> 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 wrote:
>> > @dumanshu
>> > first read my soution just above yours :)
>> >
>> >
>> >
>> >
>> >
>> > On Mon, Jul 18, 2011 at 10:21 PM, Dumanshu 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 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
Re: [algogeeks] Re: Long string and the first non-repeating character
0(n) time o(1) spcae(Dont be too harsh please I am just using 64 bytes of
extra space)
#include
#include
#include
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 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 {
> 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 wrote:
> > @dumanshu
> > first read my soution just above yours :)
> >
> >
> >
> >
> >
> > On Mon, Jul 18, 2011 at 10:21 PM, Dumanshu 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 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 >
> > > 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.
[algogeeks] Re: Long string and the first non-repeating character
@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 arr[i])
{
min = arr[i];
index = i;
}
}
now print i as %c, its the answer.
On Jul 18, 10:03 pm, sagar pareek wrote:
> @dumanshu
> first read my soution just above yours :)
>
>
>
>
>
> On Mon, Jul 18, 2011 at 10:21 PM, Dumanshu 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 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
> > 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.
Re: [algogeeks] Re: Long string and the first non-repeating character
use hash table.characters count will be stored on the basis of their ascii
value . ie a's count will be stored in array[97] .
at last just check the count of each . count==1 gives u the first non
repeating character
On Tue, Jul 19, 2011 at 12:31 AM, aditi garg wrote:
> @sagar ur solution is very gud...bt wat abt blank spaces and capital
> alphabets dat may be thr...i dnt think it will take care of that...
>
>
> On Mon, Jul 18, 2011 at 11:32 PM, varun pahwa wrote:
>
>> @sagar: that's what i have done i have taken two variables x and y which
>> can show if repetition is there or not. and we can store the initial
>> positions in the array in that case u don't have to traverse the string
>> twice.
>>
>>
>> On Mon, Jul 18, 2011 at 10:33 PM, sagar pareek wrote:
>>
>>> @dumanshu
>>> first read my soution just above yours :)
>>>
>>> On Mon, Jul 18, 2011 at 10:21 PM, Dumanshu 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 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
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
>>>
>>> --
>>> 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.
>>>
>>
>>
>>
>> --
>> Varun Pahwa
>> B.Tech (IT)
>> 7th Sem.
>> Indian Institute of Information Technology Allahabad.
>> Ph : 09793899112
>> Official Email :: rit2008...@iiita.ac.in
>> Another Email :: varunpahwa.ii...@gmail.com
>>
>> People who fail to plan are those who plan to fail.
>>
>> --
>> 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.
>>
>
>
>
> --
> Aditi Garg
> Undergraduate Student
> Electronics & Communication Divison
> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
> Sector 3, Dwarka
> New Delhi
>
> 9718388816
>
> --
> 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.
>
Re: [algogeeks] Re: Long string and the first non-repeating character
@sagar ur solution is very gud...bt wat abt blank spaces and capital
alphabets dat may be thr...i dnt think it will take care of that...
On Mon, Jul 18, 2011 at 11:32 PM, varun pahwa wrote:
> @sagar: that's what i have done i have taken two variables x and y which
> can show if repetition is there or not. and we can store the initial
> positions in the array in that case u don't have to traverse the string
> twice.
>
>
> On Mon, Jul 18, 2011 at 10:33 PM, sagar pareek wrote:
>
>> @dumanshu
>> first read my soution just above yours :)
>>
>> On Mon, Jul 18, 2011 at 10:21 PM, Dumanshu 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 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
>>> 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
>>
>> --
>> 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.
>>
>
>
>
> --
> Varun Pahwa
> B.Tech (IT)
> 7th Sem.
> Indian Institute of Information Technology Allahabad.
> Ph : 09793899112
> Official Email :: rit2008...@iiita.ac.in
> Another Email :: varunpahwa.ii...@gmail.com
>
> People who fail to plan are those who plan to fail.
>
> --
> 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.
>
--
Aditi Garg
Undergraduate Student
Electronics & Communication Divison
NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
Sector 3, Dwarka
New Delhi
9718388816
--
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.
Re: [algogeeks] Re: Long string and the first non-repeating character
@sagar: that's what i have done i have taken two variables x and y which can
show if repetition is there or not. and we can store the initial positions
in the array in that case u don't have to traverse the string twice.
On Mon, Jul 18, 2011 at 10:33 PM, sagar pareek wrote:
> @dumanshu
> first read my soution just above yours :)
>
> On Mon, Jul 18, 2011 at 10:21 PM, Dumanshu 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 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
>> 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
>
> --
> 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.
>
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112
Official Email :: rit2008...@iiita.ac.in
Another Email :: varunpahwa.ii...@gmail.com
People who fail to plan are those who plan to fail.
--
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.
Re: [algogeeks] Re: Long string and the first non-repeating character
@dumanshu
first read my soution just above yours :)
On Mon, Jul 18, 2011 at 10:21 PM, Dumanshu 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 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
> 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
--
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.
[algogeeks] Re: Long string and the first non-repeating character
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 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 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.
