Accepted O(n) solution


  • 72
    H
    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.


  • 0
    I

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


  • 8
    R

    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 "";
        }
    }

  • 1
    S

    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


  • 0
    P

    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;
    }

  • 0
    C

    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. : )


  • 0
    C

    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.


  • 6
    Z

    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);
        }
    }
    

  • 0
    N

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


  • 0
    R

    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);
    }
    

    }


  • 0
    J

    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.


  • 0
    T

    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);
    }
    

    };


  • 0
    G

    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);
        }
    };

  • 0
    N

    It's really fantastic


  • 0
    N

    This code reminds me some codes related to semaphore.


  • 0
    S

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


  • 1
    L

    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;
        }
    };

  • 0
    Q

    elegant solution!


  • 0
    S

    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.


  • 0

    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.


Log in to reply
 

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