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 saurab...@gmail.com wrote:
0(n) time o(1) spcae(Dont be too harsh please I am just using 64 bytes of
extra space)
#includebitset
#includeiostream
#includequeue
using namespace std;
int main()
{
char answer;
bitset26 charset;
bitset26 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;ji;j++)
{
if(!repeat.test(a[j]-'a')){
couta[j]endl;
return 0;
}
}
cerrNo non repeating Characterendl;
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;istr.length;i++)
{
if(arr[str[i]])
arr[str[i]] = -1;
else
arr[str[i]] = (++count);
}
set min = str.length;
index =0;
for(i=0;i26;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
values1.
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.
--
You received this message
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 aaron.nar...@gmail.comwrote:
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 saurab...@gmail.comwrote:
0(n) time o(1) spcae(Dont be too harsh please I am just using 64 bytes of
extra space)
#includebitset
#includeiostream
#includequeue
using namespace std;
int main()
{
char answer;
bitset26 charset;
bitset26 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;ji;j++)
{
if(!repeat.test(a[j]-'a')){
couta[j]endl;
return 0;
}
}
cerrNo non repeating Characterendl;
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;istr.length;i++)
{
if(arr[str[i]])
arr[str[i]] = -1;
else
arr[str[i]] = (++count);
}
set min = str.length;
index =0;
for(i=0;i26;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
values1.
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
[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 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 values1.
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.
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 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 values1.
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
--
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 sagarpar...@gmail.comwrote:
@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
values1.
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
--
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
@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 varunpahwa2...@gmail.comwrote:
@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 sagarpar...@gmail.comwrote:
@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
values1.
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
--
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
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 aditi.garg.6...@gmail.comwrote:
@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 varunpahwa2...@gmail.comwrote:
@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 sagarpar...@gmail.comwrote:
@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
values1.
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
--
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.
--
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
0(n) time o(1) spcae(Dont be too harsh please I am just using 64 bytes of
extra space)
#includebitset
#includeiostream
#includequeue
using namespace std;
int main()
{
char answer;
bitset26 charset;
bitset26 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;ji;j++)
{
if(!repeat.test(a[j]-'a')){
couta[j]endl;
return 0;
}
}
cerrNo non repeating Characterendl;
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;istr.length;i++)
{
if(arr[str[i]])
arr[str[i]] = -1;
else
arr[str[i]] = (++count);
}
set min = str.length;
index =0;
for(i=0;i26;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
values1.
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.
