O(N) template for Minimum Size Subarray Sum & Minimum Window Substring & Longest Substring Without Repeating Characters


  • 40

    First , I will show you the solution of this problem,

    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int start=0, end=0;
            int minLen=INT_MAX, sum=0;
            while(end<nums.size()){
                if(sum<s) sum+=nums[end];
                end++;
                while(sum>=s){
                    if(end-start<minLen)
                        minLen=end-start;
                    sum-=nums[start];
                    start++;
                }
            }
            return minLen==INT_MAX ? 0 : minLen;
        }
    };
    

    Next, let me show you the solution to the problem "Minimum Window Substring"

    class Solution {
    public:
        string minWindow(string s, string t) {
            vector<int> v(128, 0);
            for(auto c:t) v[c]++;
            int start=0, end=0, counter=t.size();
            int m_start=0, m_len=INT_MAX;
            while(end<s.size()){
                if(v[s[end]]>0)  counter--;
                v[s[end]]--;
                end++;
                /** loop from start to check whether we can find more short string **/
                while(counter==0){
                    if(m_len>end-start){
                        m_start=start;
                        m_len=end-start;
                    }
                    v[s[start]]++;
                    if(v[s[start]]>0) counter++;
                    start++;
                }
            }
            return m_len==INT_MAX ? "" : s.substr(m_start, m_len);
        }
    };
    

    The solution for the problem "Longest Substring Without Repeating Characters" can also be solved in the

    same pattern .

    Here is the solution for "Longest Substring Without Repeating Characters"

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            vector<int> v(128, 0);
            int start=0, end=0;
            int m_len=INT_MIN;
            while(end<s.size()){
                if(v[s[end]]==0) m_len=max(m_len, end-start+1);
                v[s[end]]++;
                end++;
                while(v[s[end]]>0){
                    v[s[start]]--;
                    start++;
                }
            }
            return m_len==INT_MIN ? 0 : m_len;
        }
    };
    

    As you can see, they all follow the same pattern !

    This post deserves your up vote!


  • 0
    F

    Really excellent summarizations !!!!


  • 2

    Thank you for showing the similarities, never paid attention to it. This is the code in Python:

    class Solution(object):
        def minSubArrayLen(self, k, nums):
            if not nums or not k: return 0
            count, i, j, n, res = 0, 0, 0, len(nums), float('inf')
            while j < n:
                if count < k: 
                    count += nums[j]
                j += 1
                while i <= j and count >= k:
                    res = min(res, j - i)
                    count -= nums[i]
                    i += 1
            return res if res < float('inf') else 0
    
    class Solution(object):
        def minWindow(self, s, t):
            i, j, n, res, miss = 0, 0, len(s), "#", len(set(t))
            freq, sofar = cl.Counter(t), cl.defaultdict(int)
            while j < n:
                if miss and s[j] in freq:
                    sofar[s[j]] += 1
                    if sofar[s[j]] == freq[s[j]]: 
                        miss -= 1
                j += 1
                while i <= j and not miss:
                    if res == "#" or len(res) > len(s[i:j]):
                        res = s[i:j]
                    if s[i] in freq:
                        sofar[s[i]] -= 1
                        if sofar[s[i]] == freq[s[i]] - 1:
                            miss += 1
                    i += 1
            return "" if res == "#" else res
    
    class Solution(object):
        def lengthOfLongestSubstring(self, s):
            i, j, reps, res, freq = 0, 0, 0, 0, cl.defaultdict(int)
            while j < len(s):
                if not reps:
                    freq[s[j]] += 1
                    if freq[s[j]] == 2:
                        reps += 1
                    else:
                        res = max(res, j - i + 1)
                j += 1
                while i <= j and reps:
                    freq[s[i]] -= 1
                    if freq[s[i]] == 1:
                        reps -= 1
                    i += 1
            return res
    

  • 0
    F

    Here is a more concise solution for the Longest Substring Without Repeating Characters

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            vector<int> m(256, -1);
            int res = 0, left = -1;
            for (int i = 0; i < s.size(); i++) {
                left = max(left, m[s[i]]);
                m[s[i]] = i;
                res = max(res, i - left);
            }
            return res;
        }
    };
    

  • 0
    F
    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int start = 0, end = 0;
            int minLen = INT_MAX, sum = 0;
            while (end < nums.size()) {
                sum += nums[end];
                end++;
                while(sum >= s) {
                    if (end - start < minLen)
                        minLen = end - start;
                    sum -= nums[start];
                    start++;
                }
            }
            return minLen == INT_MAX ? 0 : minLen;
        }
    };

Log in to reply
 

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