[algogeeks] Long string and the first non-repeating character
You are given a long string and you have to print the first non repeating character. Solve it keeping SC and TC in mind. That is present both solutions, one with high SC and low TC and viceversa. -- 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] Long string and the first non-repeating character
one solution could be:
#includestdio.h
#includestring.h
char non_repetition(char *p,int size)
{
int i,j,flag=0;
for(i=0;isize;i++)
{
for(j=0;jsize;j++)
{
if(j==i)
continue;
if(p[i]==p[j])
flag=1;
}
if(flag==0)
return p[i];
else
flag=0;
}
return '\0';
}
int main()
{
char
str[]=aaabccc
*V*;
int len=strlen(str);
char firstNR=non_repetition(str,len);
if(firstNR=='\0')
printf(all are repeating at least once\n);
else
printf(first non repeated character is=%c\n,firstNR);
return 0;
}
gives *V* as the output
On Mon, Jul 18, 2011 at 6:45 PM, Dumanshu duman...@gmail.com wrote:
You are given a long string and you have to print the first non
repeating character.
Solve it keeping SC and TC in mind. That is present both solutions,
one with high SC and low TC and viceversa.
--
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.
--
best wishes!!
Vaibhav
DU-MCA
--
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] Long string and the first non-repeating character
can anybody tell me in O(n) solution,? -- 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] Long string and the first non-repeating character
Assuming string as only lower case characters.
now declare two unsigned int as x,y and ar[26].
now when u encounter any character c among (a,...z) first time u will set
(c-'a') bit of x and check if it has already been occurred then set (c-'a')
bit of y.and ar[i] will be storing the very first occurrence of the c
character where i will be (c-'a').
now traverse the array and output will be (i+'a') where a[i] is min and
(ith) bit in x is set and ith bit in y bit is unset.
On Mon, Jul 18, 2011 at 7:26 PM, vaibhav shukla vaibhav200...@gmail.comwrote:
one solution could be:
#includestdio.h
#includestring.h
char non_repetition(char *p,int size)
{
int i,j,flag=0;
for(i=0;isize;i++)
{
for(j=0;jsize;j++)
{
if(j==i)
continue;
if(p[i]==p[j])
flag=1;
}
if(flag==0)
return p[i];
else
flag=0;
}
return '\0';
}
int main()
{
char
str[]=aaabccc
*V*;
int len=strlen(str);
char firstNR=non_repetition(str,len);
if(firstNR=='\0')
printf(all are repeating at least once\n);
else
printf(first non repeated character is=%c\n,firstNR);
return 0;
}
gives *V* as the output
On Mon, Jul 18, 2011 at 6:45 PM, Dumanshu duman...@gmail.com wrote:
You are given a long string and you have to print the first non
repeating character.
Solve it keeping SC and TC in mind. That is present both solutions,
one with high SC and low TC and viceversa.
--
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.
--
best wishes!!
Vaibhav
DU-MCA
--
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] Long string and the first non-repeating character
O(n) for both space and time... count the number of times each character is coming = O(n) space in worst case start from the string beginning if character has count == 1 print it O(n) in worst case this works with ASCII characters... since we can hash them on their values 0, 255.. for languages like hindi, german don't know :) On Mon, Jul 18, 2011 at 7:35 PM, hary rathor harry.rat...@gmail.com wrote: can anybody tell me in O(n) solution,? -- 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] Long string and the first non-repeating character
In that case only the size of hash table will be required to increase.Any possible o(1) space o(n) soln? On Mon, Jul 18, 2011 at 7:43 PM, shady sinv...@gmail.com wrote: O(n) for both space and time... count the number of times each character is coming = O(n) space in worst case start from the string beginning if character has count == 1 print it O(n) in worst case this works with ASCII characters... since we can hash them on their values 0, 255.. for languages like hindi, german don't know :) On Mon, Jul 18, 2011 at 7:35 PM, hary rathor harry.rat...@gmail.comwrote: can anybody tell me in O(n) solution,? -- 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. -- 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.
Re: [algogeeks] Long string and the first non-repeating character
Any possible o(1) space o(n) soln? O(1) space and O(n) time complexity ? On Mon, Jul 18, 2011 at 7:46 PM, saurabh singh saurab...@gmail.com wrote: In that case only the size of hash table will be required to increase.Any possible o(1) space o(n) soln? On Mon, Jul 18, 2011 at 7:43 PM, shady sinv...@gmail.com wrote: O(n) for both space and time... count the number of times each character is coming = O(n) space in worst case start from the string beginning if character has count == 1 print it O(n) in worst case this works with ASCII characters... since we can hash them on their values 0, 255.. for languages like hindi, german don't know :) On Mon, Jul 18, 2011 at 7:35 PM, hary rathor harry.rat...@gmail.comwrote: can anybody tell me in O(n) solution,? -- 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. -- 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 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] Long string and the first non-repeating character
assuming lower case characters.
#include iostream
#include string
#include limits.h
#include string.h
using namespace std;
int main ()
{
unsigned int x,y;
int ar[26];
string s;
cin s;
x = 0;
y = 0;
int l;
int min = INT_MAX;
unsigned int i = 0;
memset(ar,-1,sizeof(ar));
for(i = 0; i s.size(); i++)
{
l = s[i] - 'a';
/*first occurrence*/
if(!((1 (l)) x))
{
ar[l] = i;
x = x|(1 l);
}
else {
y = y|(1 l);
}
}
//cout x y endl;
for(i = 0; i 26; i++)
{
//cout ar[i] endl;
if(ar[i] == -1)
continue;
if(min ar[i] (!((1i)y))) {
min = ar[i];
l = i;
}
}
cout (char) (l + 'a') endl;
return 0;
}
On Mon, Jul 18, 2011 at 7:55 PM, shady sinv...@gmail.com wrote:
Any possible o(1) space o(n) soln?
O(1) space and O(n) time complexity ?
On Mon, Jul 18, 2011 at 7:46 PM, saurabh singh saurab...@gmail.comwrote:
In that case only the size of hash table will be required to increase.Any
possible o(1) space o(n) soln?
On Mon, Jul 18, 2011 at 7:43 PM, shady sinv...@gmail.com wrote:
O(n) for both space and time...
count the number of times each character is coming = O(n) space in worst
case
start from the string beginning if character has count == 1 print it O(n)
in worst case
this works with ASCII characters... since we can hash them on their
values 0, 255.. for languages like hindi, german don't know :)
On Mon, Jul 18, 2011 at 7:35 PM, hary rathor harry.rat...@gmail.comwrote:
can anybody tell me in O(n) solution,?
--
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.
--
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 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] Long string and the first non-repeating character
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.
Re: [algogeeks] Long string and the first non-repeating character
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.
