Sharing my 340ms C++ solution


  • 0
    T
    class Solution {
    private:
        bool containAll(vector<int>& count)
        {
            for(int i=0; i<count.size(); i++)
            {
                if(count[i] < 0)
                    return false;
            }
                
            return true;
        }
        
    public:
        string minWindow(string s, string t) {
            vector<int> count(256, 0);
            int n = t.length();
            int i;
            for(i=0; i<n; i++)
                count[t[i]]--;
                
            int LEFT=0, RIGHT=0, left=0, right=0;
            
            n = s.length();
            int minLength = n+1;
            
            while(right<n)
            {
                count[s[right]]++;
                while(containAll(count))
                {
                    if(minLength>right-left+1)
                    {
                        minLength = right-left+1;
                        LEFT = left;
                        RIGHT = right;
                    }
                    count[s[left]]--;
                    left++;
                }
                right++;
            }
            
            if(minLength == n+1)
                return "";
            else
                return s.substr(LEFT, RIGHT-LEFT+1);
        }
    };

Log in to reply
 

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