Ashish
BAN USERAlgorithm :
Let P[] has the required unique and beautiful string and let s[] has the input string.
For each character c in s do the following steps :-
1) check for occurrence of c in P.
if(not found)
append c in P;
else
{
p1=position of c in P;
find character c1 in P after p1 which is lexicographically greater than c;
if(c1 found)
{
p2=position of c1 in P;
see whether characters between p1 and p2 are repeated in input string after c;
if(yes)
{
shift all characters from p1+1 to left by 1 position in P;
P[end]=c;
}
}
}
#include<stdio.h>
int main()
{
char s[1000000];
int p[257],i,j,f,r,p1,p2,k,t;
scanf("%s",s);
for(i=0;i<257;i++)
p[i]=-1;
for(i=0;s[i]!='\0';i++)
{
r=1;
p1=-1;
p2=-1;
for(j=0;p[j]!=-1;j++)
{
if(p1==-1 && p[j]==s[i])
{
p1=j;
for(k=j+1;p[k]!=-1;k++)
{
if(p[k]>s[i])
{
p2=k;
break;
}
}
if(p2>-1)
{
for(k=p1+1;k<p2;k++)
{
r=0;
for(t=i+1;s[t]!='\0';t++)
{
if(s[t]==p[k])
{
r=1;
break;
}
}
if(r==0)
break;
}
}
}
if(p2>-1 && r==1)
p[j]=p[j+1];
}
if(p2>-1 && r==1)
p[j-1]=s[i];
else if(p1==-1)
p[j]=s[i];
}
printf("\n");
for(i=0;p[i]!=-1;i++)
printf("%c",p[i]);
return 0;
}
if all the internal modes in BST have only one child then its preorder has a special property i.e. every element is min or max of all the succeeding elements.
let there be n elements in preorder.
check(int p[])
{
int min,max,i;
if(p[n-1]<p[n-2])
{
min=p[n-1];
max=p[n-2];
}
else
{
min=p[n-2];
max=p[n-1];
}
for(i=n-3;i>=0;i--)
{
if(p[i]>max)
max=p[i];
else if(p[i]<min)
min=p[i];
else
return 0;
}
return 1;
}
@babbupandey : in order to keep the most lexicographically greater characters on left preserving the order, this happens.
- Ashish August 20, 2012