[Leetcode] Sliding Window Summary

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn‘t one, return 0 instead.

Example: 

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        const int n = nums.size();
        int l = 0, r = 0, sum = s, res = n + 1;
        while (r < n) {
            sum -= nums[l];
            while (r + 1 < n && sum > 0) {
                sum -= nums[++r];
            }
            res = min(res, r - l);
            l = ++r;
        }
        return res;
    }
};

Variation 2:
class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            if (nums.size() == 0) return 0;
            int size = nums.size();
            int l = 0;
            int sum = 0;
            int ret = INT_MAX;
            for (int i = 0; i < size; ++i) {
                sum += nums[i];
                while (sum >= s) {
                    ret = min(ret, i - l + 1);
                    sum -= nums[l++];
                }
            }
            return ret == INT_MAX ? 0 : ret;
        }
};

Variation 3:
class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            if (nums.size() == 0) return 0;
            int size = nums.size();
            int l = 0;
            int sum = 0;
            int ret = INT_MAX;
            for (int i = 0; i < size; ++i) {
                sum += nums[i];
                while (sum >= s) {
                    ret = min(ret, i - l + 1);
                    sum -= nums[l++];
                }
            }
            return ret == INT_MAX ? 0 : ret;
        }
};


https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.
If there is no non-empty subarray with sum at least K, return -1.


Example 1:
Input: A = [1], K = 1
Output: 1


Example 2:
Input: A = [1,2], K = 4
Output: -1


Example 3:
Input: A = [2,-1,2], K = 3
Output: 3


Note:

1 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9

Everything is the same, except with negative integer(s) in the array

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C%2B%2BJavaPython-O(N)-Using-Deque
Q: Why keep the deque increase?A: If B[i] <= B[d.back()] and moreover we already know that i > d.back(), it means that compared with d.back(),B[i] can help us make the subarray length shorter and sum bigger. So no need to keep d.back() in our deque.

More detailed on this, we always add at the LAST positionB[d.back] <- B[i] <- ... <- B[future id]B[future id] - B[d.back()] >= k && B[d.back()] >= B[i]B[future id] - B[i] >= k too

so no need to keep B[d.back()]
What is the purpose of second while loop?
To keep B[D[i]] increasing in the deque.
Why keep the deque increase?
If B[i] <= B[d.back()] and moreover we already know that i > d.back(), it means that compared with d.back(),B[i] can help us make the subarray length shorter and sum bigger. So no need to keep d.back() in our deque.
  int shortestSubarray(vector<int> A, int K) {
        int N = A.size(), res = N + 1;
        deque<int> d;
        for (int i = 0; i < N; i++) {
            if (i > 0)
                A[i] += A[i - 1];
            if (A[i] >= K)
                res = min(res, i + 1);
            while (d.size() > 0 && A[i] - A[d.front()] >= K)
                res = min(res, i - d.front()), d.pop_front();
            while (d.size() > 0 && A[i] <= A[d.back()])
                d.pop_back();
            d.push_back(i);
        }
        return res <= N ? res : -1;
    }


https://leetcode.com/problems/minimum-window-substring/
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.


Variation 1:
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> m;
        for (char c : t) {
            m[c]++;
        }
        int sz = m.size();
        string res;
        for (int i = 0, j = 0, cnt = 0; i < s.size(); ++i) {
            if (m[s[i]] == 1)
                cnt++;
            m[s[i]]--;
            while (m[s[j]] < 0) {
                m[s[j++]]++;
            }
            
            if (cnt == sz) {
                if (res.empty() || res.size() > i - j + 1)
                    res = s.substr(j, i - j + 1);
            }
        }
        return res;
    }
};

Variation 2:
class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> v(128, 0);
        for (char c : t)
            v[c]++;
        int start = 0, end = 0, head = 0, counter = t.size (), len = INT_MAX;
        while (end < s.size ())
        {
            if (v[s[end++]]-- > 0) counter--;
            while (counter == 0)
            {
                if (end - start < len) 
                {
                    len = end - start;
                    head = start;
                }
                if (v[s[start++]]++ == 0) counter++;
            }
        }
        return len == INT_MAX ? "" : s.substr (head, len);
    }
};

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.Variation 1:

#define vi vector<int>
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        const int n = s.size();
        vi v(128, 0);
        int i = 0, j = 0, res = 0;
        while (i < n) {
            v[s[i]]++;
            while (j < n && v[s[i]] > 1)
                v[s[j++]] --;
            res = max(res, j - i + 1);
            i++;
        }
        return res;
    }
};

int recommend(string s)
    {
        vector<int> v(128, 0);
        int start = 0, end = 0, d = 0, counter = 0;
        while (end < s.size()) {
            if (v[s[end++]]++ > 0)
                counter++;
            while (counter > 0) {
                if (v[s[start++]]-- > 1)
                    counter--;
            }
            d = max(d, end - start);
        }
        return d;
    }

Input: "eceba"
Output: 3
Explanation: tis "ece" which its length is 3.

Input: "ccaabbb"
Output: 5
Explanation: tis "aabbb" which its length is 5.

int lengthOfLongestSubstringTwoDistinct(string s) {
        vector<int> map(128, 0);
        int counter=0, begin=0, end=0, d=0; 
        while(end<s.size()){
            if(map[s[end++]]++==0) counter++;
            while(counter>2) if(map[s[begin++]]--==1) counter--;
            d=max(d, end-begin);
        }
        return d;
    }

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> m;
        for (char c : t) {
            m[c]++;
        }
        int sz = m.size();
        string res;
        for (int i = 0, j = 0, cnt = 0; i < s.size(); ++i) {
            if (m[s[i]] == 1)
                cnt++;
            m[s[i]]--;
            while (m[s[j]] < 0) {
                m[s[j++]]++;
            }
            
            if (cnt == sz) {
                if (res.empty() || res.size() > i - j + 1)
                    res = s.substr(j, i - j + 1);
            }
        }
        return res;
    }
};

string minWindow(string s, string t) {
        vector<int> map(128,0);
        for(auto c: t) 
            map[c]++;
        int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
        while(end<s.size()){
            if(map[s[end++]]-->0) 
                counter--; //in t
            while(counter==0){ //valid
                if(end-begin<d)  
                    d=end-(head=begin);
                if(map[s[begin++]]++==0) 
                    counter++;  //make it invalid
            }  
        }
        return d==INT_MAX? "":s.substr(head, d);
    }