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


  • 0
    E
    /**
     * 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
    	HashMap<Character, LinkedList<Integer>> cnt = new HashMap<Character, LinkedList<Integer>>();
    	//store the indexes of all chars
    	LinkedList<Integer> inds = new LinkedList<Integer>();
    	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)){
    				LinkedList<Integer> indice = new LinkedList<Integer>();
    				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);
    }

  • 1
    C

    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;
    import java.util.LinkedHashSet;
    import java.util.LinkedList;
    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)
    	    HashMap<Character, LinkedList<Integer>> hashIdxes = new HashMap<Character, LinkedList<Integer>>();
    	    // 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
            // so use LinkedHashSet 
            LinkedHashSet<Integer> hashIdx = new LinkedHashSet<Integer>();
            // 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)) {
    	          LinkedList<Integer> queue = new LinkedList<Integer>();
    	          queue.add(i);
    	          hashIdxes.put(c, queue);
    	          hashIdx.add(i);
    	          countT--;
    	        } else if(hashIdxes.get(c).size()<freq) {
    	          hashIdxes.get(c).add(i);
    	          hashIdx.add(i);
    	          countT--;
    	        } else {
    	          int deletedIdx = hashIdxes.get(c).poll();
    	          hashIdxes.get(c).add(i);
    	          hashIdx.remove(deletedIdx);
    	          hashIdx.add(i);
    	          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);
    	  }
    }

Log in to reply
 

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