# Got TLE when tested by the longest case. I don't know why? I think My solution is O(n)

• ``````/**
* Given a string S and a string T, find the minimum window in S
*  which will contain all the characters in T in complexity O(n).
* @param S
* @param T
* @return
*/
public String minWindow(String S, String T) {
if(S.length()<T.length())
return "";
//store the char in T and its Corresponding number
HashMap<Character, Integer> cn = new HashMap<Character, Integer>();
//store the index of each char in S
//store the indexes of all chars
int ct = 0;//mark the chars in current window
int gLen = S.length()+1;
int gMin = 0;
int gMax = 0;
//caculate the number of each differenc
for(int i=0;i<T.length();i++){
char tmp = T.charAt(i);
if(cn.containsKey(tmp))
cn.put(tmp, cn.get(tmp)+1);
else
cn.put(tmp, 1);
}

//traverse the String S
for(int i=0;i<S.length();i++){
char tmp = S.charAt(i);
//if tmp is one of the char in T, else do nothing
if(cn.containsKey(tmp)){
int num = cn.get(tmp); // the total time of occurrence
//update cnt map
if(!cnt.containsKey(tmp)){
indice.offer(i);
cnt.put(tmp, indice);
ct++;
inds.offer(i);
}else if(cnt.get(tmp).size()<num){
cnt.get(tmp).offer(i);
ct++;
inds.offer(i);
}else {
Integer r = cnt.get(tmp).remove();//remove the oldest one
cnt.get(tmp).offer(i);
inds.remove((Object)r);
inds.offer(i);
}
//has contain all the chars
if(ct == T.length()){
int min = inds.get(0);
int max = inds.get(inds.size()-1);
if( max-min+1<gLen){
gLen = max-min+1;
gMin = min;
gMax = max;
}
}
}
}
return gLen == S.length()+1 ? "" : S.substring(gMin, gMax+1);
}``````

• Hey echoht,

I think the idea of your solution is very clear, at least to me. However it seems that the operation LinkedList.remove(Object r) is linear time. So I use LinkedHashSet to replace it, and also maintain the head and tail index of current window. Here is my modification based on your solution.

``````import java.util.HashMap;
import java.util.Iterator;
public class Solution {
public String minWindow(String S, String T) {
if(S==null||T==null||S.length()==0||T.length()==0||S.length()<T.length())
return "";
// mapping T into hash
HashMap<Character, Integer> hashT = new HashMap<Character, Integer>();
// maintain a queue of index for each (non-duplicated) character (within current window)
// maintain a queue of index for current window
// There will be some queue.remove(Object o) operations,
// if use LinkedList, then it is linear time to remove an element
// since we also need to get the head and tail index of current window,
// and it cannot be retrieved directly from LinkedHashSet in O(1) time,
// we need two varaibles to maintain the head and tail index
int hashIdxL = -1, hashIdxR = -1;
// record how many characters needed from S
int countT = T.length();
// if there is a solution, minLen <= S.length()
int minLen = S.length() + 1;
// record the index of minimum window until now
int l = 0, r = S.length() - 1;
// hash T into HashMap
for(char c : T.toCharArray()) {
if(hashT.containsKey(c)) {
hashT.put(c, hashT.get(c)+1);
} else hashT.put(c, 1);
}
// traverse the String S
for(int i=0;i<S.length();i++) {
char c = S.charAt(i);
// if c is in T, else do nothing
if(hashT.containsKey(c)) {
// maintain the head and tail of current window
if(hashIdxL==-1) hashIdxL = i;
hashIdxR = i;
// the char frequency in T
int freq = hashT.get(c);
if(!hashIdxes.containsKey(c)) {
hashIdxes.put(c, queue);
countT--;
} else if(hashIdxes.get(c).size()<freq) {
countT--;
} else {
int deletedIdx = hashIdxes.get(c).poll();
hashIdx.remove(deletedIdx);
if(deletedIdx==hashIdxL) {
Iterator<Integer> iter = hashIdx.iterator();
if(iter.hasNext())
hashIdxL = iter.next();
}
}
// already found all the chars of T in S
if(countT==0) {
if(hashIdxR-hashIdxL+1<minLen) {
l = hashIdxL;
r = hashIdxR;
minLen = r - l + 1;
}
}
}
}
return minLen == S.length()+1 ? "" : S.substring(l, r+1);
}
}``````

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