int main()

{

char str[] = "Rajat Grover is a good boy";

char set[] = "aio";

int lenStr = strlen(str);

int lenSet = strlen(set);

int minDist = 32767; //Some very large value

int maxInd = lenStr;

int minInd = -1;

bool allFound = false;

char *hashSet = new char[lenSet];

for(int i=0; i<lenSet; hashSet[i++] = -1);

for(i=0; i<lenStr; ++i)

{

int ind = -1;

if(-1 != (ind = Index(set, str[i], lenSet)))

{

hashSet[ind] = i;

if(!allFound)

{

allFound = true;

for(int j=0; j<lenSet; ++j)

{

if(hashSet[j] == -1)

{

allFound = false;

break;

}

}

if(!allFound)

continue;

}

int tempMax, tempMin;

int tempDistance = (tempMax = Max(hashSet,lenSet)) - (tempMin =

Min(hashSet,lenSet));

if(minDist > ++tempDistance)

{

maxInd = tempMax;

minInd = tempMin;

if((minDist = tempDistance) == lenSet)

break;

}

}

}

cout<<"Minimum Interval: "<<minDist<<". Between index "<<minInd

<<" and "<<maxInd<<'\n';

return 0;

}

Hi

ReplyDeleteI didn't get the algorithm here. Can you please post the algorithm.

@Swapnil, Algorithm is straight forward... Just traverse the string from the start and if any of the character from the set encountered, add/update the index of that character until all characters from the set are not found. Once all characters are found, take the distance as maxIndex-minIndex + 1 and stored as minDistance.

ReplyDeleteAfter this whenever you encountered any set character, update the index, compute the distance and compare it with minDistance and update minDistance = distance computed if distance computed < minDistance.

Can you modify it for char set having repeated characters, like s1 = 'Grover is a good boy'

ReplyDeletes2 = 'oago'

?? Surely current implementation will not work.

Thanks for pointing out the mistake. I will modify accordingly.

Delete