143_leetcode_Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

1:注意特殊情况；2:设置两个大小为256的int数组，needFound和hasFound分别代表在T中需要查找的字符类型和个数以及已经在S中查找的类型和个数；3:设置start和end两个指针分别遍历数组，在遍历的过程中，进行相应的处理。

    string minWindow(string S, string T)
    {
        if(S.length() == 0 || T.length() == 0 || S.length() < T.length())
        {
            return "";
        }
        
        string result = "";
        int start = 0;
        int end = 0;
        int count = 0;
        int number = (int)T.length();
        int minLength = (int)S.length() + 1;
        int minStart = -1;
        
        int needFound[256] = {0};
        int hasFound[256] = {0};
        
        for(int i = 0; T[i] != '\0'; i++)
        {
            needFound[T[i]] += 1;
        }
        
        for(; S[end] != '\0'; end++)
        {
            if(needFound[S[end]] == 0)
            {
                continue;
            }
            
            hasFound[S[end]] += 1;
            if(hasFound[S[end]] <= needFound[S[end]])
                count++;
            
            if(count == number)
            {
                while(needFound[S[start]] == 0 || hasFound[S[start]] > needFound[S[start]])
                {
                    if(hasFound[S[start]] > needFound[S[start]])
                    {
                        hasFound[S[start]]--;
                    }
                    start++;
                }
                
                int tmpLength = end - start + 1;
                if(tmpLength < minLength)
                {
                    minLength = tmpLength;
                    minStart = start;
                }
            }
        }
        return minStart == -1 ? "" : S.substr(minStart, minLength);
    }