Flipkart Question: Find the minimum window in a large string which contains all characters of another string.

Problem: Given a large string S and a smaller string T. Find the minimum size window in the string S which contains all the characters of the string T.

Solution:

• Maintain two pointers to store the begin and end positions of the window, two hash tables needToFind to store total count of a character in T and found to store total count of a character met so far and a count variable to store the total characters in T that's met so far. When count equals T's length, a valid window is found.
• Each time the end pointer is advanced, we increment hasFound[S[end]] by one. Increment count by one if hasFound[S[end]] is less than or equal to needToFind[S[end]]. If count equals to lengh of T then begin pointer can be advanced until found[S[begin]] is greater than needToFind[S[begin]].
• Finally we just need to set minWindowSize to currentWindowSize if currentWindowSize is less than currentWindowSize.

Implementation:

bool minWindow(std::string S, std::string T, int &minWindowBegin,  int &minWindowEnd)

{

int lenS = S.size();

int lenT = T.size();

int needToFind[256] = {0};

int found[256] = {0};

for(int i = 0; i < lenT; ++i)

needToFind[T[i]]++;

int minWindowLen = INT_MAX;

int count = 0;

for(int begin = 0, end = 0; end < lenS; ++end)

{

if(needToFind[S[end]] == 0)

continue;

found[S[end]]++;

if(found[S[end]] <= needToFind[S[end]])

++count;

if(count == lenT)

{

while(needToFind[S[begin]] == 0 || found[S[begin]] > needToFind[S[begin]])

{

if(found[S[begin]] > needToFind[S[begin]])

--found[S[begin]];

++begin;

}

int currWindowLen = end - begin + 1;

if(currWindowLen < minWindowLen)

{

minWindowBegin = begin;

minWindowEnd = end;

minWindowLen = currWindowLen;

}

}

}

return count == lenT;

}

Complexity: O(n) where n is length of S.