paresh.nakhe
BAN USERCode is not as clean as I would have liked.....but this will solve it in O(n) time.
void copy(char max[], char *source, char *dest)
{
int j=0;
for(char *i = source; i != dest; i++)
max[j++] = *i;
max[j] = '\0';
cout << max << endl;
}
int main()
{
set<char> myset;
set<char>::iterator it;
char str[] = "bbbbb";
char *tmp, *hold;
tmp = hold = str;
char max[10];
int crnt_len=0;
while(*tmp != '\0'){
it = myset.find(*tmp);
if( it != myset.end()){
if(tmp - hold > crnt_len){
crnt_len = tmp-hold;
copy(max, hold, tmp);
}
do{
myset.erase(*hold);
hold++;
}
while(*hold != *tmp);
myset.erase(*hold);
hold++;
}
myset.insert(*tmp);
tmp++;
}
if(tmp - hold > crnt_len){
crnt_len = tmp-hold;
copy(max, hold, tmp);
}
cout << max << endl;
return 0;
}
tmp pointer starts from the first character and continues till it encounters a repeated character. Here hold pointer marks the beginning of the current max string. When you find a repeated character, you increment your hold pointer, store the string seen till now (as max) and erase the corresponding character from set.
- paresh.nakhe November 16, 2012Easier way is to use an array of 256 elements to check for repetition. Sorry if the code looks messy.
In other words, hold and tmp shall traverse once. Hence O(N)