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). For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC". Note: If there is no such window in S that covers all characters in T, return the emtpy string "". If there are multiple such windows, you are guaranteed…

LeetCode-Minimum Window Substring

C++:
class Solution {
public:
    string minWindow(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(T.length()==0||S.length()<T.length()) return "";
        int sLen=S.length();
        int tLen=T.length();
        int ct1[256];
        int ct2[256];
        memset(ct1,0,sizeof(ct1));
        memset(ct2,0,sizeof(ct2));
        for(int i=0;i<tLen;i++){
            ct1[T[i]]++;
            ct2[T[i]]++;
        }
        int start=0;
        int minStart=0;
        int minLen=sLen+1;
        int count=tLen;
        for(int end=0;end<sLen;end++){
            if(ct2[S[end]]>0){
                ct1[S[end]]--;
                if(ct1[S[end]]>=0) count--;
            }
            if(count==0){
                while(true){
                    if(ct2[S[start]]>0){
                        if(ct1[S[start]]<0) ct1[S[start]]++;
                        else break;
                    }
                    start++;
                }
                if(end-start+1<minLen){
                    minStart=start;
                    minLen=end-start+1;
                }
            }
        }
        if(minLen==sLen+1) return "";
        return S.substr(minStart,minLen);
    }
};
Java:
public class Solution {
    public String minWindow(String S, String T) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(T==null||T.length()==0) return "";
        if(S==null||S.length()<T.length()) return "";
        int sLen=S.length();
        int tLen=T.length();
        char[] s1=S.toCharArray();
        char[] t1=T.toCharArray();
        int[] ct1=new int[256];
        int[] ct2=new int[256];
        for(int i=0;i<tLen;i++){
            ct1[t1[i]]++;
            ct2[t1[i]]++;
        }
        int start=0;
        int minStart=0;
        int minLen=sLen+1;
        int count=tLen;
        for(int end=0;end<sLen;end++){
            if(ct2[s1[end]]>0){
                ct1[s1[end]]--;
                if(ct1[s1[end]]>=0) count--;
            }
            if(count==0){
                while(true){
                    if(ct2[s1[start]]>0){
                        if(ct1[s1[start]]<0) ct1[s1[start]]++;
                        else break;
                    }
                    start++;
                }
                if(end-start+1<minLen){
                    minLen=end-start+1;
                    minStart=start;
                }
            }
        }
        if(minLen==sLen+1) return "";
        return S.substring(minStart,minStart+minLen);
    }
}