C++ solution with runtime 17ms.


  • 2
    B

    what we need is to move the ''second" pointer to the right and check the "first" pointer ,
    make it is possible to constuct the shortest required string.

        class Solution {
    public:
        string minWindow(string S, string T) {
            
            string str = "";
            int lenS = (int)S.size();
            int lenT = (int)T.size();
            if (lenT == 0) return str;
            int minLen = lenS + 1;
            int num[256], count[256];
            memset(num, 0, sizeof(num));
            memset(count, 0, sizeof(count));
            
            for (int index = 0; index < (int)T.size(); index++) 
                num[(int)T[index]]++;
            int first = 0, second = 0;
            int chaCount = 0;
            while (second < lenS) {
                int secCha = (int)S[second];
                if (++count[secCha] <= num[secCha]) {
                    chaCount++;
                }
                if (chaCount == lenT) {
                    while (first <= second) {
                        int firCha = (int)S[first];
                        if (count[firCha] > num[firCha]) 
                            count[firCha]--, first++;
                        else break;
                    }
                    if (minLen > second - first + 1) {
                       minLen = second - first + 1;
                       str = S.substr(first, minLen);
                    }
                }
                second++;
            }
            return str;       
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.