Tuesday, May 26, 2015

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.

  • 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.


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)

int minWindowLen = INT_MAX;
int count = 0;
for(int begin = 0, end = 0; end < lenS; ++end)
if(needToFind[S[end]] == 0)
if(found[S[end]] <= needToFind[S[end]])
if(count == lenT)
while(needToFind[S[begin]] == 0 || found[S[begin]] > needToFind[S[begin]])
if(found[S[begin]] > needToFind[S[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.

No comments:

Post a Comment