A simple C++ solution.


  • 0
    D
    class Solution {
    public:
        string minWindow(string s, string t){
            
            int hashMap[256] = {0};
    
            int m = s.size();
            int n = t.size();
            
            for(int i = 0; i < n; ++ i) hashMap[t[i]] ++;
            
            int minLen = INT_MAX, len = 0, validLen = 0;
            string minRet = "", ret = "";
            
            for(int i = 0; i < m; ++ i){
                
                if(hashMap[s[i]] > 0) validLen ++;
                hashMap[s[i]] --;
                len ++;
                ret.push_back(s[i]);
                
                while(hashMap[ret[0]] < 0){
                    hashMap[ret[0]] ++;
                    ret.erase(ret.begin());
                    len --;
                }
                
                if(validLen == n && len < minLen){
                    minLen = len;
                    minRet = ret;
                }
            }
            
            return minRet;
        }
    };
    

    I am not sure about the time complexity, because copy from ret to minRet is O(n). If you have any idea, please leave your comment.


Log in to reply
 

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