Monday, November 15, 2010

DirectI Question: You are given a large string of characters and a small set of characters. You have to find smallest substring of String which contains all characters in the Set.

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;

}

4 comments:

  1. Hi

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

    ReplyDelete
  2. @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.
    After 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.

    ReplyDelete
  3. Can you modify it for char set having repeated characters, like s1 = 'Grover is a good boy'
    s2 = 'oago'
    ?? Surely current implementation will not work.

    ReplyDelete
    Replies
    1. Thanks for pointing out the mistake. I will modify accordingly.

      Delete