C++ 10 lines 12ms


  • 1
    B

    char counter uses char as index can save bunch of time over map<char,int>
    the index of returning string is bestL and bestR

    class Solution {
    public:
        string minWindow(string s, string t) 
        {
            int count[256] = {0};
            int len=t.length(), bestL=-1, bestR=-1, left=0;
            for(auto e : t) count[e]++;
            
            for( int i = 0; i < s.length(); i++ )
            {
                if(count[s[i]]>0) len--;
                count[s[i]]--;
                while(count[s[left]]<0)
                {
                    count[s[left]]++;
                    if(count[s[left]]>0) len++;
                    left++;
                }
                if( len==0 && (bestL==-1 || i-left<bestR-bestL )) bestL=left, bestR=i;
            }
            
            return bestL<0 ? "" : s.substr(bestL, bestR-bestL+1);
        }
    };

  • 0
    H

    This code is so amazing,I can understand it!!!
    but I can't understand why you should add this:
    if(count[s[left]]>0) len++;
    I just remove this sentence, and I can still pass all test cases


  • 0
    B
    if(count[s[left]]>0) len++;
    

    count[s[left]] is the count of char, if it is non-positive, we have this char in the window, if it is positive, we do not have enough quantity of this char in the window, so we need to increment len, where len is the number of char from t but out of window.


Log in to reply
 

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