A 9ms O(n) C++ solution


  • 1

    Here is a 9 ms C++ solution, it's an O(n) solution. Let me explain later.

    Let M = s.size(), N = t.size();

    • First, we keep 2 pointers, i and j, which points to the end and start of the substring. i and j are initialized to 0.
    • For i from 0 to N-1, first include s[i] into substring. This may cause more than enough s[i], so we will pop from the j-side. while we have more than enough s[j], we increase j by 1, else we stop it. After this, we have the shortest substring that ends at i.
    • If substring between j and i is enough, then we get a solution.

    We can just count each character in t and substring, then we compare each character to make sure if we get a qualified substring, but we can do it better : each time we add a char (s[i]), we check if we have enough s[i] before. If not, we count it as a valid number. If we get N valid number, we know that the substring is qualified. In this way we don't have to do much comparisions.

    class Solution {
    public:
        string minWindow(string s, string t) {
            int M = t.size();
            int src[128] = {0}, target[128] = {0};
            for (auto item : t) target[item]++;
            
            int cur_len = 0, min_len = INT_MAX, valid_count = 0;
            string result = "";
            
            char ch;
            
            int i = 0, j = 0;
            for (; i < s.size(); i++) {
                ch = s[i];
                // add s[i]
                if (src[ch] < target[ch] && target[ch]>0) valid_count++;
                cur_len++;
                src[ch]++;
                
                // check if we can pop any from j
                ch = s[j];
                while (target[ch] == 0 || src[ch] > target[ch]) {
                    src[ch]--;
                    j++;
                    cur_len--;
                    ch = s[j];
                }
                
                if (cur_len < min_len && valid_count>=M) {
                    min_len = cur_len;
                    result = s.substr(i-cur_len+1, cur_len);
                }
            }
            
            return result;
        }
    };
    

Log in to reply
 

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