12 ms C++ O(N) time O(1) space


  • 0
    F
    class Solution {
    public:
        string minWindow(string s, string t) {
            if (t.empty())
                return "";
            int t_map[256] = {0}, s_map[256] = {0};
            int t_size = 0;
    
            for (auto c : t)
            {
                if (t_map[c] == 0)
                    t_size ++;
                t_map[c] ++;
            }
            int start = 0, end = 0, found = 0, min_start = 0, min_end = s.size() + 1;
            while (start <= end && end <= s.size())
            {
                if (found < t_size)
                {
                    end ++;
                    char c = s [end - 1];
                    if (t_map[c] > 0 && ++s_map[c]  ==  t_map[c])
                    {
                        found ++;
                    }
                }else {
                    start ++;
                    char c = s [start - 1];
                    if (t_map[c] > 0 && s_map[c]--  ==  t_map[c])
                    {
                        found --;
                    }
                }
                if (found == t_size && end - start < min_end - min_start)
                {
                    min_start = start;
                    min_end = end;
                }
            }
            if (min_end == s.size() + 1)
                return "";
            return s.substr(min_start, min_end - min_start);
        }
    };

Log in to reply
 

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