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

• 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!

• Really excellent summarizations !!!!

• 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
``````

• 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;
}
};
``````

• ``````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;
}
};``````

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