Binary search and two pointers

LeetCode 76 Minimum Window Substring

Runtime: 292 ms, faster than 6.73% of C++ online submissions for Minimum Window Substring.Memory Usage: 379.2 MB, less than 5.01% of C++ online submissions for Minimum Window Substring.
class Solution {
public:
string minWindow(string s, string t) {
int low = t.length(), high =s.length();
const int n = s.length();
const int M = 256;
int min_ = 128, max_ = -1;
vector<vector<int>> cnt(n+1, vector<int>(M, 0));
for (int i =0; i < n; ++i)
{
min_ = min(int(s[i]), min_);
max_ = max(int(s[i]), max_);
cnt[i+1] = cnt[i];
cnt[i+1][s[i]] += 1;
}
vector<int> cnt_t(M, 0);

for (auto c : t)
{
min_ = min(int(c), min_);
max_ = max(int(c), max_);
cnt_t[c] += 1;
}
function<string(int)> good = [=](int k)
{
string ret = "";
for (int i = k-1; i < n; ++i)
{
bool good = true;
// if from 0 to 127 will get TLE.
for (int j =min_ ; j <= max_; ++j)
if (cnt[i+1][j] - cnt[i-k+1][j] < cnt_t[j])
{
good = false;break;
}
if (good)return s.substr(i -k+1, k);
}
return ret;
};

while (low <high)
{
int mid = low + (high - low)/2;
if (good(mid)!="")
{
high = mid;
}
else
{
low = mid + 1;
}
}
return good(low);

}
};

O(n) solution [1]

Runtime: 12 ms, faster than 98.83% of C++ online submissions for Minimum Window Substring.Memory Usage: 7.6 MB, less than 88.85% of C++ online submissions for Minimum Window Substring.

For this code, we count down to indicate whether we have collected enough elements within the window of [i, j].

For example

if s = “aaab”

and t is ‘aab’

then we need 2 a and 1 b.

we traverse from left to right of the s

i = 0, j = 0 :  
we get 1 'a', we still need 1 a and 1b, we use need['a'] = 1, need['b'] = 1, found = 1;
i = 0, j = 1 : 'a', need['a'] = 0, need['b'] = 1, found = 2;
i = 0, j = 2 : 'a', need['a'] = -1, need['b'] = 1, found = 2;
i = 0, j = 3 : 'b', need['a'] = -1, need['b'] = 0, found =3 == t.length() we find a valid window. However, this window maybe too large. We look from the i to see whether we can reduce the window size given a fixed j.
look from left:
when i = 0: remove one 'a', need['a'] = 0
whem i = 1, remove one 'a', need['a'] = 1 > 0, we can not move this 'a', which means we can not make the window size smaller. This is a smallest window size given the j. We get the answer.
class Solution {
public:
string minWindow(string s, string t)
{
vector<int> m(128,0);
for(auto c: t) m[c]++;
int cnt = t.length(), i = 0, j = 0, d = INT_MAX, head = 0;
while( j < s.length())
{
if(m[s[j]] > 0 )
{
cnt--;
}
m[s[j]]--;++j;
while(cnt == 0) // valid result
{
if(j - i < d) {d = j - i; head = i;}
m[s[i]]++;
if(m[s[i]] == 1) cnt++; //make it invalid
++i;
}
}
return d==INT_MAX? "":s.substr(head, d);
}
};
class Solution {
public:
string minWindow(string s, string t)
{
const int N = s.length(), M = t.length();
vector<int> n(128, 0), m(128,0);
for(auto c: t) m[c]++;
int cnt = 0, i = 0, j = 0, d = INT_MAX, head = 0;
while( j < s.length())
{
if(n[s[j]] < m[s[j]])
{
cnt++;
}
n[s[j]]++;++j;
while(cnt == M) // valid result
{
if(j - i < d) {d = j - i; head = i;}
if(n[s[i]] == m[s[i]]) cnt--; //make it invalid
n[s[i]]--;
++i;
}
}
return d==INT_MAX? "":s.substr(head, d);
}
};

We can also rewrite the code by using for loops instead of while loop.

class Solution {
public:
string minWindow(string s, string t)
{
const int N = s.length(), M = t.length();
vector<int> n(128, 0), m(128,0);
for(auto c: t) m[c]++;
int cnt = 0, i = 0, j = 0, d = INT_MAX, head = 0;
for (int j = 0; j < N; ++j)
{
auto c = s[j];
if(n[c] < m[c]) cnt++;
n[c]++;
while(cnt == M) // valid result
{
if(j - i +1 < d) {d = j - i + 1; head = i;}
if(n[s[i]] == m[s[i]]) cnt--; //make it invalid
n[s[i]]--;
++i;
}
}
return d==INT_MAX? "":s.substr(head, d);
}
};

Reference

[1]https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems

Data Scientist/MLE/SWE @takemobi