Minimum Window Substring

• Time:O(|\texttt{s}| + |\texttt{t}|)
• Space:O(128) = O(1)

C++

``````class Solution {
public:
string minWindow(string s, string t) {
vector<int> count(128);
int required = t.length();
int bestLeft = -1;
int minLength = s.length() + 1;

for (const char c : t)
++count[c];

for (int l = 0, r = 0; r < s.length(); ++r) {
if (--count[s[r]] >= 0)
--required;
while (required == 0) {
if (r - l + 1 < minLength) {
bestLeft = l;
minLength = r - l + 1;
}
if (++count[s[l++]] > 0)
++required;
}
}

return bestLeft == -1 ? "" : s.substr(bestLeft, minLength);
}
};
``````

JAVA

``````class Solution {
public String minWindow(String s, String t) {
int[] count = new int[128];
int required = t.length();
int bestLeft = -1;
int minLength = s.length() + 1;

for (final char c : t.toCharArray())
++count[c];

for (int l = 0, r = 0; r < s.length(); ++r) {
if (--count[s.charAt(r)] >= 0)
--required;
while (required == 0) {
if (r - l + 1 < minLength) {
bestLeft = l;
minLength = r - l + 1;
}
if (++count[s.charAt(l++)] > 0)
++required;
}
}

return bestLeft == -1 ? "" : s.substring(bestLeft, bestLeft + minLength);
}
}
``````

Python

``````class Solution:
def minWindow(self, s: str, t: str) -> str:
count = Counter(t)
required = len(t)
bestLeft = -1
minLength = len(s) + 1

l = 0
for r, c in enumerate(s):
count[c] -= 1
if count[c] >= 0:
required -= 1
while required == 0:
if r - l + 1 < minLength:
bestLeft = l
minLength = r - l + 1
count[s[l]] += 1
if count[s[l]] > 0:
required += 1
l += 1

return '' if bestLeft == -1 else s[bestLeft: bestLeft + minLength]
``````