# Accepted O(n) solution

• ``````class Solution {
public:
string minWindow(string S, string T) {
if (S.empty() || T.empty())
{
return "";
}
int count = T.size();
int require[128] = {0};
bool chSet[128] = {false};
for (int i = 0; i < count; ++i)
{
require[T[i]]++;
chSet[T[i]] = true;
}
int i = -1;
int j = 0;
int minLen = INT_MAX;
int minIdx = 0;
while (i < (int)S.size() && j < (int)S.size())
{
if (count)
{
i++;
require[S[i]]--;
if (chSet[S[i]] && require[S[i]] >= 0)
{
count--;
}
}
else
{
if (minLen > i - j + 1)
{
minLen = i - j + 1;
minIdx = j;
}
require[S[j]]++;
if (chSet[S[j]] && require[S[j]] > 0)
{
count++;
}
j++;
}
}
if (minLen == INT_MAX)
{
return "";
}
return S.substr(minIdx, minLen);
}
};
``````

Implementation of mike3's idea

running time : 56ms.

• Nice implement, I learned a lot from your code. Thanks a lot :)

• A java implementation

``````public class Solution {
public String minWindow(String S, String T) {

if (S.length()==0||T.length()==0||S.length()<T.length()) return "";

int left=T.length(),start=-1,end=S.length();

Deque<Integer> queue= new LinkedList<Integer>();

Map<Character,Integer> map= new HashMap<Character,Integer>();

for (int i=0;i<T.length();i++){
char c= T.charAt(i);
map.put(c,map.containsKey(c)?map.get(c)+1:1);
}

for (int i =0;i<S.length();i++){
char c= S.charAt(i);
if (!map.containsKey(c))
continue;

int n = map.get(c);
map.put(c,n-1);
queue.add(i);
if (n>0) left--;

char head = S.charAt(queue.peek());
while(map.get(head)<0){
queue.poll();
map.put(head,map.get(head)+1);
head=S.charAt(queue.peek());
}

if (left==0){
int new_length=queue.peekLast()-queue.peek()+1;
if (new_length<end-start) {
start=queue.peek();
end=queue.peekLast()+1;
}
}
}
if (left==0)  return S.substring(start,end);
else return "";
}
}``````

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

• Share my solution

``````string minWindow(string S, string T) {
string res = "";
int tCharNum[256] = {0};
int sCharNum[256] = {0};
int l = 0,r = 0;

for (int i = 0; i < T.size(); i++)
tCharNum[T[i]] ++;

while (r < S.size())
{
if (tCharNum[S[r]])
{
sCharNum[S[r]]++;
while (check(sCharNum, tCharNum))
{
if (res == "" || res.size() > (r - l + 1)) res = S.substr(l, r - l + 1);
if (sCharNum[S[l]])     sCharNum[S[l]]--;
do { l++; } while (l < S.size() && tCharNum[S[l]] == 0);
}
}
r++;
}
return res;
}

bool check(int * t1, int * t2)
{
for (int i = 0; i < 256; i++)
if (t1[i] < t2[i]) return false;
return true;
}``````

• I'm afraid a problem comes up when S = "CDE" and T = "AB" work on this part

``````if (count)
{
i++;
require[S[i]]--;
if (chSet[S[i]] && require[S[i]] >= 0)
{
count--;
}
}
``````

since S has nothing in common in T, count will always be positive which leads to the indexing on S illegal by S[3] here.

Anyway, this minor problem won't affect the brilliant implementation. Bravo on the good job. : )

• A question: what if i == S.size()-1 && count > 0 when at start of the while loop? Then "i" will increment and thus got to S.size() and S[i] will overflow.

• In java, two HashMap or one HashMap + one HashSet are not necessary.
Similar idea: I use one HashMap can represent requires as:
char -> Integer i:

• i>0 need more; i==0 require satisfied; i<0 got extras;

And,
count: only use for first pass to check if requires satisfied. Also, it was used for check the final return.
Check Here: java minimum window substring

``````public class Solution {
public static String minWindow(String S, String T) {
int minlen = S.length();
int minstart = 0;
int minend = S.length()-1;
HashMap<Character, Integer> require = new HashMap<Character, Integer>();
for(int i=0; i<T.length(); i++) {
char c = T.charAt(i);
require.put(c, require.containsKey(c)? require.get(c)+1 : 1);
}
int count = T.length();
int left = 0;   // left, i index included in substring
for(int i=0; i<S.length(); i++) {
char c = S.charAt(i);
// move right pointer
if(require.containsKey(c)) {
if(require.get(c)>0) count--;  // extra char does not affect count
require.put(c, require.get(c)-1);
}

// move left pointer
if(count==0) {  // require satisfied, count only use for first time require satisfied
char cleft = S.charAt(left);
while(!require.containsKey(cleft) || require.get(cleft) < 0) {  // not required char OR have extra, can move
if(require.containsKey(cleft)) {
require.put(cleft, require.get(cleft)+1);
}
left ++;
cleft = S.charAt(left);
}
// update index
if(minlen>i-left+1) {
minstart = left;
minend = i;
minlen=i-left+1;
}
}
}
if(count!=0) return"";  // !!!
return S.substring(minstart, minend+1);
}
}
``````

• I see, if T has two same char, window must contains two same char.

• share my solution

import java.util.Enumeration;
import java.util.Hashtable;
import java.util.List;
import java.util.ArrayList;

public class Solution {
private class E {
int total = 0;
List<Integer> ls = new ArrayList<Integer>();
}

``````public String minWindow(String S, String T) {
if ( S == null || T == null || S.length() == 0 || T.length() == 0 ) {
return "";
}
Hashtable<Character,E> m = new Hashtable<Character,E>();
for ( int i = 0; i < T.length(); i++) {
char c = T.charAt(i);
E e = m.get(c);
if ( e == null ) {
e = new E();
m.put(c,e);
}
e.total += 1;
}
int fStart = -1,fEnd = S.length();
int len = S.length() + 1;
for ( int i = 0; i < S.length(); i++ ) {
char c = S.charAt(i);
E e = m.get(c);
if ( e != null ) {
if ( e.ls.size() >= e.total ) {
e.ls.remove(0);
}
e.ls.add(i);
boolean all = true;
int start = S.length(),end = 0;
for ( Enumeration<E> em = m.elements(); all && em.hasMoreElements(); ) {
E t = em.nextElement();
all = t.total == t.ls.size();
}
if ( all ) {
for ( Enumeration<E> em = m.elements(); em.hasMoreElements(); ) {
E t = em.nextElement();
start = Math.min(start,t.ls.get(0));
end = Math.max(end,t.ls.get(t.total-1));
}
}
if ( all && end - start < len ) {
len = end - start;
fEnd = end;
fStart = start;
}
}
}
return fStart == -1 ? "" : S.substring(fStart,fEnd+1);
}
``````

}

• cuero, I think you are right, S[i] is not a valid character. But it won't throw an exception either. I think S[i] still returns something, for example "\0", and it quickly goes to the next loop where "i == (int)S.size()" and the loop ends.

• Here is my version using one unordered_map, basically the same implementation as the @heleifz

``````class Solution {
public:
//https://oj.leetcode.com/discuss/5469/is-the-length-of-t-considered-constant-or-m
string minWindow(string S, string T) {
string result;
if(S.empty()||T.empty())
return "";
unordered_map<char, int> hash; //value represents the times of this letter appearing during [start, end]
int minLen = INT_MAX, minIndex = 0;
int count = T.size();
for(int i=0; i<count; ++i)
hash[T[i]]++;
int start=0,end=0;
while(start<S.size()&&end<S.size()+1)
{
if(count>0)//check current substring [start,end] to see if it contains all letters in T
{
if(hash.find(S[end])!=hash.end())
{
hash[S[end]]--;
if(hash[S[end]]>=0)//this letter is the first appearing from [start, end], so we count it
count--;
}
end++;
}
else//here [start, end] contains all letters in T;
{
if(minLen>end - start)
{
minLen = end - start;
minIndex = start;
}
if(hash.find(S[start])!=hash.end())
{
hash[S[start]]++;
if(hash[S[start]]>0)//also, this letter is the only one appearing from [start, end], so we count it
count++;
}
start++;
}
}
if(minLen==INT_MAX)
return "";
return S.substr(minIndex, minLen);
}
``````

};

• My solution, run in O(n)

``````class Solution {
public:
string minWindow(string S, string T) {
if (T.size() == 0) {
return "";
}
vector<int> alpha(256, 0), count(256, 0);
int alpha_size = 0, count_size = 0;

for (int i = 0; i < T.size(); i++) {
alpha[T[i]]++;
if (alpha[T[i]] == 1) {
alpha_size++;
}
}

int l = 0, r = 0, minv = S.size() + 10, minv_l = 0, minv_r = 0;
while (true) {
while (r < S.size() && count_size < alpha_size) {
if (alpha[S[r]] > 0) {
count[S[r]]++;
if (count[S[r]] == alpha[S[r]]) {
count_size++;
}
}
r++;
}
if (count_size < alpha_size) {
break;
}

while (l <= r && count_size == alpha_size) {
if (alpha[S[l]] > 0) {
if (count[S[l]] == alpha[S[l]]) {
count_size--;
}
count[S[l]]--;
}
l++;
}

if (minv > r - l + 1) {
minv = r - l + 1;
minv_l = l - 1;
minv_r = r;
}

}

return S.substr(minv_l, minv_r - minv_l);
}
};``````

• It's really fantastic

• This code reminds me some codes related to semaphore.

• I meet the same problem(s[i] will overflow.) when I run it in VS2010 platform.

• completed in C++
46 lines---simple

``````class Solution {
public:
string minWindow(string s, string t) {
string res="",tmp="";
if(t=="" || s=="")
return res;
int i=0,j=0,len0=s.size(),len1=t.size();
int mark0[128],mark1[128];//设置两个数组来判断是否包含了t的所有字符；由于字符都是ACSII，所以设置数组大小为128；
memset(mark0,0,sizeof(mark0));
memset(mark1,0,sizeof(mark0));
for(i=0;i<len1;++i)
{
++mark1[int(t[i])];//在mark1[]数组中统计t中字符出现的个数，为判断是否包含了t中所有字符提供一个标砖
}
while(j<len0 && !isall(mark0,mark1))//实现滑动窗口机制：如果tmp没有包含t中所有字符，那么s[j]字符继续放入tmp中；如果tmp包含了t中所有字符，那么tmp就循环试着删除首字符直到没再包含t中所有字符为止；
{
tmp.push_back(s[j]);
++mark0[int(s[j])];
while(isall(mark0,mark1))
{
if(res.empty())
{
res=tmp;
}
else
{
if(tmp.size()<res.size())
res=tmp;
}
--mark0[int(tmp[0])];
tmp.erase(tmp.begin());
}
++j;
}
return res;
}
bool isall(int *m0,int *m1)
{
for(int i=0;i<128;++i)
{
if(m0[i]<m1[i])
return false;
}
return true;
}
};``````

• elegant solution!

• in the case "a", "a" , the i will go out of range, you should make sure the i is not out of s index range, so after i++ you should make sure i < n.

• Hi, @sornor. You may try it in Microsoft Visual Studio 2013. The code will be Ok. I wonder whether it is due to its supported C++ 11 standard? The OJ also supports C++ 11.

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