Minimum Window Substring

Question

Given a set T of characters and a string S, find the minimum window in S which will contain all the characters in T in complexity O(n).

eg,
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 that there will always be only one unique minimum window in S.

Answer 1

This is an interesting problem and interesting problems have multiple approaches and the best approach is usually simple and beautiful.

In this post, I illustrate my approach when I first attempt this problem. My first approach is more complicated and is not the best solution (runs in O(N lg M) time). Later in this post, I explain the best approach which runs in O(N) time with the help of images.

Hint:
Using the above example S = "ADOBECODEBANC" and T = "ABC", we can easily find the first window which contains T is "ADOBEC". Another possible candidate is "ADOBECODEBA". In fact, we should skip this, because within it exists a sub-window "CODEBA" that is both shorter and satisfy the constraint. The final window to consider is "BANC", which is also the minimum window.

To solve this problem efficiently, below are the two key points we need to consider:

How do we determine if a particular window contains T? (ideally in O(1) time)

How do we select all windows efficiently? (ideally do not include other windows that wrap about a sub-window)

We definitely need the help from a hash table here. Hash table is able to tell us if a letter exist in T in O(1) time.

An O(N lg M) solution:
When I first approach this problem, I thought of having another table which records the position of last-met character in T. That is, when I first see 'A', I record its position being 0. Each time I see 'A' again, I replace its position with the new position. This approach is simple but flawed. Notice that T does not include duplicate characters? If T includes duplicate characters, such as "AABC", this approach does not work.

In this case, the remedy is to maintain queues (instead of table) that correspond to each unique character in T. For example, assume that T = "AABC", when you first see 'A', push its position into the 'A' queue (which originally is empty). When you see 'A' again, push its position to the back of 'A' queue. The third time you see 'A', you would pop the front element, and push its position to the back of 'A' queue. By popping the element, we do not include window that wrap around a sub-window. This approach works but the difficulty is two-fold:

There is no way we could determine the starting and ending position of a window directly from the queue itself. A naive way is to scan the entire queue for minimum and maximum value.

How do we determine if the window satisfies the constraint? We would have to scan all queues to check if the sum of all queues' sizes is equal to T's length.

The way I solve the above problem is to maintain a sorted map that maps indices to character so that we can grab the minimum and maximum position in O(1) time. But there is an extra cost for doing this. Each time you pop an element from the queue, you would also need to update the map by deleting the corresponding element and inserting a new element. To check if the window satisfies the constraint, we check the map's size; a valid window is found if the map's size is equal to T's length.

The complexity of the method is O(N lg M), where N is the length of S, and M is the length of T. The extra lg M term is due to the extra cost of deleting and inserting an element in the map, where each costs O(lg M) time in the worst case (Note that M is the map's maximum size. Why?)

// Returns false if no valid window is found. Else returns
// true and updates minWindowBegin and minWindowEnd with the
// starting and ending position of the minimum window.
bool findMinWindow(const char *str, const char *pattern,
                   int &minWindowBegin, int &minWindowEnd) {
    int N = strlen(str);
    int M = strlen(pattern);
    int minWindowLen = INT_MAX;

    // hash table init all to 0s
    // used to check how many letters left in T to be filled
    int needToFill[256] = {0};

    for (int i = 0; i < M; i++)
        needToFill[pattern[i]]++;

    // set the rest to -1 so we know that letter is not in T
    for (int i = 0; i < 256; i++)
        if (needToFill[i] == 0)
            needToFill[i] = -1;

    // array of queues, each corresponds to a unique char in T
    queue<int> q[256];

    // maintains a sorted map (maps indices to char),
    // the first and last element tells us the
    // starting and ending position of the window
    map<int,char> m;

    for (int i = 0; i < N; i++) {
        // skips characters not in T
        if (needToFill[str[i]] == -1) continue;

        // push character to queue
        if (q[str[i]].size() < needToFill[str[i]]) {
            q[str[i]].push(i);
            m[i] = str[i];
        }
        // replace the character in the queue
        // and updates the corresponding element in the map
        else {
            int idxToErase = q[str[i]].front();
            map<int,char>::iterator it = m.find(idxToErase);
            m.erase(it);
            m[i] = str[i];
            q[str[i]].pop();
            q[str[i]].push(i);
        }

        // found a window, check for minimum
        if (m.size() == M) {
            int end = m.rbegin()->first;
            int begin = m.begin()->first;
            int windowLen = end - begin + 1;
            if (windowLen < minWindowLen) {
                minWindowLen = windowLen;
                minWindowBegin = begin;
                minWindowEnd = end;
            }
        } // end if
    } // end for

    return (m.size() == M) ? true : false;
}

Best solution:
The best solution, is in fact simpler. This best approach is suggested by someone who called stormrage.

Notice how complicated the above solution is. It uses a hash table, a queue, and a sorted map. During an interview, the problems tend to be short and the solution usually can be coded in about 50 lines of code. So be sure that you say out loud what you are thinking and keep communication opened with the interviewer. Check if your approach is unnecessary complex, he/she might be able to give you guidance. The last thing you want to do is to get stuck in a corner and keep silent.

To help illustrate this approach, I use a different example: S = "acbbaca" and T = "aba". The idea is mainly based on the help of two pointers (begin and end position of the window) and two tables (needToFind and hasFound) while traversing S. needToFind stores the total count of a character in T and hasFound stores the total count of a character met so far. We also use a count variable to store the total characters in T that's met so far (not counting characters where hasFound[x] exceeds needToFind[x]). When count equals T's length, we know a valid window is found.

Each time we advance the end pointer (pointing to an element x), we increment hasFound[x] by one. We also increment count by one if hasFound[x] is less than or equal to needToFind[x]. Why? When the constraint is met (that is, count equals to T's size), we immediately advance begin pointer as far right as possible while maintaining the constraint.

How do we check if it is maintaining the constraint? Assume that begin points to an element x, we check if hasFound[x] is greater than needToFind[x]. If it is, we can decrement hasFound[x] by one and advancing begin pointer without breaking the constraint. On the other hand, if it is not, we stop immediately as advancing begin pointer breaks the window constraint.

Finally, we check if the minimum window length is less than the current minimum. Update the current minimum if a new minimum is found.

Essentially, the algorithm finds the first window that satisfies the constraint, then continue maintaining the constraint throughout.

i) S = "acbbaca" and T = "aba".

ii) The first minimum window is found. Notice that we cannot advance begin pointer as hasFound['a'] == needToFind['a'] == 2. Advancing would mean breaking the constraint.

iii) The second window is found. begin pointer still points to the first element 'a'. hasFound['a'] (3) is greater than needToFind['a'] (2). We decrement hasFound['a'] by one and advance begin pointer to the right.

iv) We skip 'c' since it is not found in T. Begin pointer now points to 'b'. hasFound['b'] (2) is greater than needToFind['b'] (1). We decrement hasFound['b'] by one and advance begin pointer to the right.

v) Begin pointer now points to the next 'b'. hasFound['b'] (1) is equal to needToFind['b'] (1). We stop immediately and this is our newly found minimum window.

Both the begin and end pointers can advance at most N steps (where N is S's size) in the worst case, adding to a total of 2N times. Therefore, the run time complexity must be in O(N).

// Returns false if no valid window is found. Else returns
// true and updates minWindowBegin and minWindowEnd with the
// starting and ending position of the minimum window.
bool minWindow(const char* S, const char *T,
               int &minWindowBegin, int &minWindowEnd) {
    int sLen = strlen(S);
    int tLen = strlen(T);
    int needToFind[256] = {0};

    for (int i = 0; i < tLen; i++)
        needToFind[T[i]]++;

    int hasFound[256] = {0};
    int minWindowLen = INT_MAX;
    int count = 0;
    for (int begin = 0, end = 0; end < sLen; end++) {
        // skip characters not in T
        if (needToFind[S[end]] == 0) continue;
        hasFound[S[end]]++;
        if (hasFound[S[end]] <= needToFind[S[end]])
            count++;

        // if window constraint is satisfied
        if (count == tLen) {
            // advance begin index as far right as possible,
            // stop when advancing breaks window constraint.
            while (needToFind[S[begin]] == 0 ||
                   hasFound[S[begin]] > needToFind[S[begin]]) {
                if (hasFound[S[begin]] > needToFind[S[begin]])
                    hasFound[S[begin]]--;
                begin++;
            }

            // update minWindow if a minimum length is met
            int windowLen = end - begin + 1;
            if (windowLen < minWindowLen) {
                minWindowBegin = begin;
                minWindowEnd = end;
                minWindowLen = windowLen;
            } // end if
        } // end if
    } // end for

    return (count == tLen) ? true : false;
}

Test Cases:
» Download sample test cases with answers

Answer 2

A small improvement: add an array to keep track of visited chars in S that are also in T so that left pointer can jump directly to next spot. This will not change the big-o time though.

/*
 * Two pointers: one for window_left and one for window_right
 * As moving to the right, we know which char is in T,
 * store the index into an array so that left point can directly
 * jump to next spot.
 */
public String minWindow(String S, String T) {
    int ss = S.length(), tt = T.length();
    // set up a hashmap for T and also keep track of occurance
    HashMap<Character, Integer> needFind = new HashMap<Character, Integer>();
    HashMap<Character, Integer> hasFound = new HashMap<Character, Integer>();
    for (int i=0; i<tt; ++i) {
        hasFound.put(T.charAt(i), 0);
        if (needFind.containsKey(T.charAt(i))) {
            needFind.put(T.charAt(i), needFind.get(T.charAt(i))+1);
        } else {
            needFind.put(T.charAt(i), 1);
        }
    }
    // sliding window as needed
    int right = 0, found = 0, left = 0;
    ArrayList<Integer> nexts = new ArrayList<Integer>();
    String window = "";
    int winSize = Integer.MAX_VALUE;
    while (right < S.length()) {
        char c = S.charAt(right);
        if (!needFind.containsKey(c)) {  // not a match
            ++right;
            continue;
        }

        nexts.add(right);
        ++right;
        hasFound.put(c, hasFound.get(c)+1);
        if (hasFound.get(c) <= needFind.get(c))  ++found;

        if (found >= tt) { // got a window
            // move left?
            char ll = S.charAt(nexts.get(left));
            while (hasFound.get(ll) > needFind.get(ll)) {
                hasFound.put(ll, hasFound.get(ll)-1);
                ++left;
                ll = S.charAt(nexts.get(left));
            }
            // smaller window?
            if (right - nexts.get(left) < winSize) {
                winSize = right - nexts.get(left);
                window = S.substring(nexts.get(left), right);
            }
        }
    }
    return window;
}

Answer 3

class Solution {
public:
    string minWindow(string S, string T) {
        if (S.size()==0 || T.size()==0) return "";
        //sliding window
        // we count the number of needed copies of each char to contain T in S[slow:fast]
        // Notice that S[fast] is contained
        int slow=0, fast=0;

        vector<bool> is_in_T(256,false);        // we can also use unordered_set here
        for (int i=0; i<T.size(); ++i)  is_in_T[T[i]]=true;
        // number of copies of each char needed to contain T
        // if T = "AAA", then initially, dist['A'] = -3;
        // if dist>=0 elementwise, then we find a good window
        vector<int> dist(256, 0);
        for (int i=0; i<T.size(); ++i)  dist[T[i]]--;
        if (is_in_T[S[0]]) dist[S[0]]++;

        string min_w;   // the minimum window found so far
        int min_w_size = INT_MAX;   // the size of the minimum window
        bool have_found = false;    // if a window has been found
        while (slow<S.size() && fast<S.size()) {
            if (!is_in_T[S[slow]]) {    // it is ok to remove the S[slow] from the window
                ++slow;
                continue;
            }
            if (dist[S[slow]]>0) {
                --dist[S[slow]];
                ++slow;
            } else {
                if (!have_found)
                    have_found = is_all_non_neg(dist);  
                if (have_found && min_w_size>fast-slow+1) { // once we have found a window, the window is always good.
                    min_w_size = fast-slow+1;
                    min_w = S.substr(slow, min_w_size);
                }
                ++fast;     // the window must be extended given slow cannot move
                if (fast<S.size() && is_in_T[S[fast]]) ++dist[S[fast]];
            }

        }
        return min_w;
    }
private:
    bool is_all_non_neg(const vector<int> &v) {
        for (int i=0; i<v.size(); ++i)
            if (v[i]<0)
                return false;
        return true;
    }
};

Answer 4

Just some improvement over the best solution of the first answer: 1) determine whether the current window is valid with O(1); 2) adjust the count with O(1)

The idea is too use a doublely linked list to store the count and a hashmap to index the count.

Here is my code for this data structure:

/**
 * this class implement a fast counting table, which support following functions
 * 1    store the required counting of the target data
 * 2    quick adjust the counting
 * 3    quickly found any data which dosen't met requirement (assuming that we want all the     counting being nonpositive
 * all three operation has constant time cost
 * the idea is that, we maintain a double linked list, where the node has field data and count
 * we always make sure the node with positive count is before the node with negative count
 * which can be simply achieved by moving the node whose count is just increased to 1 to the head
 * and the node whose count is just decreased to 0 to the tail
 * @author qzhang53
 *
 */
public class QuickCountTable <Anytype extends Comparable<Anytype>> {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    QuickCountTable<Character> list1=new QuickCountTable<Character>();
    String T="xbnpukocakzqzuhdlxoga";
    for(int i=0; i<T.length(); i++)
    {
        list1.add(T.charAt(i));
    }
    System.out.println(list1);
    String S="xeaifhaqslynbcwxncwgeezbrjorzyuwevejcecuscjvg";
    QuickCountTable<Character> list2=new QuickCountTable<Character>();
    for(int i=0; i<S.length(); i++)
    {
        list2.add(S.charAt(i));
    }
    System.out.println(list2);
}

// we will store the data into a double linked list
// we will also maintain a variable called tail to a quick insert
private QuickCountTableNode<Anytype> head, tail;
// the node of this list will be indexed via a hashmap
// key is the data and the value is the node where the count of this data is stored
private HashMap<Anytype, QuickCountTableNode<Anytype>> list;

// constructor
public QuickCountTable()
{
    head=null;
    tail=null;
    list=new HashMap<Anytype, QuickCountTableNode<Anytype>>();
}

/** 
 * this should only be used for initialize the list
 * if the data is not found in the list, we create a new node for it and set the count to 1 then move
 * it to the head
 * otherwise, we retrieve the node with the data and increase its count by 1
 */
public void add(Anytype x)
{
    // first check whether x is already included
    if (list.containsKey(x))
    {
        // we already have it in the list
        QuickCountTableNode<Anytype> node=list.get(x);
        node.cnt++;
        if (node.cnt==1)
        {
            if (node==tail)
            {
                tail=node.prev;
            }
            // this node has count<=0 before, we move it to the head
            if (node.prev!=null)
            {
                node.prev.next=node.next;
            }
            if (node.next!=null)
            {
                node.next.prev=node.prev;
            }
            node.next=head;
            if (head!=null && head!=null)
            {
                head.prev=node;
            }
            if (head!=null)
            {
                node.prev=null;
            }
            head=node;
        }
    }
    else
    {
        // we haven't met it before, we create a new node for it and insert it to the head
        QuickCountTableNode<Anytype> node=new QuickCountTableNode<Anytype>(x);
        node.cnt=1;
        node.next=head;
        if (head!=null && head!=null)
        {
            head.prev=node;
        }
        head=node;
        list.put(x, node);
    }
    // for the case the list has only one element
    if (tail==null)
    {
        tail=head;
    }
}

/**
 * when we remove a new data (e.g., shrink the window), we look it up in the hashmap
 * if it is found, we decrease its count. If it becomes 1, we move it to the head
 * otherwise, we just do nothing
 * @param x
 */
public void increase(Anytype x)
{
    // first check whether x is already included
    if (list.containsKey(x))
    {
        // we already have it in the list
        QuickCountTableNode<Anytype> node=list.get(x);
        node.cnt++;
        if (node.cnt==1)
        {
            // avoid the loop
            if (node==tail)
            {
                tail=node.prev;
            }
            // this node has count<=0 before, we move it to the head
            if (node.prev!=null)
            {
                node.prev.next=node.next;
            }
            if (node.next!=null)
            {
                node.next.prev=node.prev;
            }
            node.next=head;
            if (head!=null && head!=null)
            {
                head.prev=node;
            }
            if (head!=null)
            {
                node.prev=null;
            }
            head=node;
        }
    }
}

/**
 * when we met a new data, we look it up in the hashmap
 * if it is found, we decrease its count. If it becomes 0, we move it to the tail
 * otherwise, we just do nothing
 * @param x
 */
public void decrease(Anytype x)
{
    if (list.containsKey(x))
    {
        // we already have it in the list
        QuickCountTableNode<Anytype> node=list.get(x);
        node.cnt--;
        if (node.cnt==0)
        {
            // save the head first
            if(node==head)
            {
                head=node.next;
            }
            // this node has count>0 before, we move it to the tail
            if (node.prev!=null)
            {
                node.prev.next=node.next;
            }
            if (node.next!=null)
            {
                node.next.prev=node.prev;
            }
            node.next=null;
            if (tail!=null && tail!=node)
            {
                tail.next=node;
            }
            if (tail!=node)
            {
                node.prev=tail;
            }
            tail=node;
        }
    }
}

/**
 * for being valid, we require the count of all the value in the list is nonpositive
 * from the algorithm, we already make sure the value with positive count is always 
 * before the node with nonpositive count
 * thus we only need to check the first element
 * @return
 */
public boolean isValid()
{
    if(head!=null)
    {
        if (head.cnt<=0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else
    {
        return true;
    }
}

/**
 * just visualize the hashmap
 */
public String toString()
{
    StringBuffer result=new StringBuffer();
    QuickCountTableNode<Anytype> node=head;
    while(node!=null)
    {
        result.append("["+node+"]");
        node=node.next;
    }
    return result.toString();
}
}

/**
 * the class to store the count and table
 * it also maintain two references to its next and previous
 * @author qzhang53
 *
 * @param <Anytype>
 */
class QuickCountTableNode<Anytype>
{
public Anytype val;
public int cnt;
public QuickCountTableNode<Anytype> next;
public QuickCountTableNode<Anytype> prev;
public QuickCountTableNode(Anytype v)
{
    val=v;
    cnt=0;
    next=null;
    prev=null;
}

public String toString()
{
    return new String(val+","+cnt);
}
}

Here is the algorithm for this specific problem:

public class MinimumWindowSubstring {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    MinimumWindowSubstring instance=new MinimumWindowSubstring();
    System.out.println(instance.minWindow("xeaifhaqslynbcwxncwgeezbrjorzyuwevejcecuscjvgfutkrcqxbromihlgcjnzpybwcxqeglknhgzyiqxljnyrvlazvnyklbgoywugjftrltrvlrgueeobsoandazqbigbgbhqgdjtycojtwfydtbvjekmejdirjlymvquybnyddjxaoxfkyatckijvlrnwcnjxfdxgtvjweiyvfdhefaipkrnviaunpfmukkcdhlcmwcjbgqhnsqfdhsasuwhjbtfmdhrluvzqykugcbtutyzdqcxkyevaxcodjhogdpwbzsjducxpdzsvbpizvfbtirwtzmzebyhcqqfmueczdwveofgjkhesbamaolgrlpvcfcqbhubmtythdzspizijbwlqjrjvgfznhprqmudfsyoxzimhhutjsebcykxgpywznnpbhuizuwythkbohwzzacbanyhewdfmsvpzryamuyhdkkurgvrjysjntqrrvxfnuvonvqbrqjvbvpucklligu", "xbnpukocakzqzuhdlxoga"));
}

public String minWindow(String S, String T) {
    // Start typing your Java solution below
    // DO NOT write main() function/
    // we use brute force search, where the complexity is O(N^2)
    if (T==null || T.length()<1)
    {
        return new String("");
    }
    else if (S==null || S.length()<1 || S.length()<T.length())
    {
        return new String("");
    }
    else
    {
        // build the pattern
        QuickCountTable<Character> target=new QuickCountTable<Character>();
        for (int i=0; i<T.length(); i++)
        {
            target.add(T.charAt(i));
        }
        for (int i=0; i<T.length(); i++)
        {
            target.decrease(S.charAt(i));
        }
        int min_start, min_end;
        min_start=-1;
        min_end=S.length()+1;
        boolean found=false;
        int start, end;
        start=0;
        end=T.length();
        while(end<=S.length())
        {
            // we found a potential window
            // check whether it is the smallest
            if (target.isValid())
            {
                if ((min_end-min_start)>(end-start))
                {
                    min_start=start;
                    min_end=end;
                    found=true;
                }
                // find a new window by shrinking the window by 1 on the left
                target.increase(S.charAt(start));
                start++;
            }
            else if (end<S.length())
            {
                // we need to expand the window by 1 on the right
                target.decrease(S.charAt(end));
                end++;
            }
            else
            {
                break;
            }
        }
        if (found)
        {
            return S.substring(min_start, min_end);
        }
        else
        {
            return new String("");
        }
    }
}
}

Answer 5

A bit clearer solution using the 2 pointers approach in O(n):

   string minWindow(string s, string t) {
    if (t.size() == 0) return "";

    map<char,int> hist;
    for (char c : t) {
        hist[c] = 0;
    }
    for (char c : t) {
        hist[c]++;
    }

    int count = 0;
    int minstart = 0 ,minlen = s.size() + 1;
    int start = 0, end = 0;
    while (end < s.size()) {
        if (hist.find(s[end]) != hist.end()) {
            hist[s[end]]--;
            if (hist[s[end]] >= 0) count++;
            while(count == t.size()) {
                if (end - start + 1 < minlen) {
                    minlen = end - start + 1;
                    minstart = start;                            
                }  
                if (hist.find(s[start]) != hist.end()) { 
                    hist[s[start]]++;
                    if (hist[s[start]] > 0) count --;
                }
                start++;
            }
        }
        end++;
    }

    if (minlen > s.size()) return "";
    return s.substr(minstart, minlen);
}

Answer 6

string minWindow(string S, string T) {
    int T_table[256]={0}, n(S.size()), m(T.size());
    int curr_table[256]={0}, count=0, minw_L=INT_MAX, minw_B=n;
    for(int i=0; i<m; ++i) T_table[T[i]]++;
    for(int i=0, begin=0; i<n; ++i){
        if(T_table[S[i]]==0) continue;
        if(++curr_table[S[i]]<=T_table[S[i]]) count++;
        if(count!=m) continue;
        while(T_table[S[begin]]==0 || curr_table[S[begin]]>T_table[S[begin]]) 
            --curr_table[S[begin++]];
        if(minw_L>i-begin+1){
            minw_B=begin;
            minw_L=i-begin+1;
        }
    }
    return S.substr(minw_B, minw_L);
}

Answer 7

private static String findMinimumWindow(String text, String pattern)
{
    char[] textChars = text.toCharArray();
    HashMap<Character, Integer> patternCharNeeded = new HashMap<Character, Integer>();
    char[] patternChars = pattern.toCharArray();

    //initialize patternCharNeeded
    for (char ch : patternChars)
    {
        if (!patternCharNeeded.containsKey(ch))
        {
            patternCharNeeded.put(ch, 1);
        }
        else
        {
            patternCharNeeded.put(ch, 1 + patternCharNeeded.get(ch));
        }
    }

    //initialize patternCharHasFound
    HashMap<Character, Integer> patternCharHasFound = new HashMap<Character, Integer>();

    for (char ch : patternChars)
    {
        patternCharHasFound.put(ch, 0);
    }

    //use this two index to track window size
    int frontIndex = -1;
    int backIndex = -1;

    //set the original minWindow to be null
    String minWindowSofar = null;

    //now traverse the text array
    for (int i=0; i<textChars.length; i++)
    {
        char cha = textChars[i];

        //advance backIndex
        backIndex++;

        //update patternCharHasFound
        //if the char is in pattern, then update patternCharHasFound
        if (patternCharNeeded.containsKey(cha))
        {
            //initialize front index
            //skip unpattern chars in the starting positions
            if (frontIndex == -1)
            {
                frontIndex = i;
            }

            if (!patternCharHasFound.containsKey(cha))
            {
                patternCharHasFound.put(cha, 1);
            }
            else
            {
                patternCharHasFound.put(cha, 1+ patternCharHasFound.get(cha));
            }

            //compare patternCharHasFound with patternCharTotal
            //if patternCharFound contains required chars and enough counts specified in patternCharNeeded, 
            //then update minWindowSofar.
            //else if char is equal to char at front index AND its count in patternCharHasFound > its count in patternCharNeeded
            //advance front index until the char in front index's count in patternCharHasFound will be less than its count in patternCharTotal 
            //this means, continuing advancing will break the min window's constraint (all needed chars in pattern must be in min window)

            //only when a pattern char has been found, then check whether a new window has found?
            boolean hasAllPatternChars = compareTotalWithHashFound(patternCharNeeded, patternCharHasFound);
            if (hasAllPatternChars)
            {
                //found a new window, is it the min window so far?
                //minWindowSofar is null when it is not initialized
                //otherwise, update minWindowSofar only when new window size is less than the existing min window so far
                if (minWindowSofar == null || backIndex-frontIndex+1 < minWindowSofar.length())
                {
                    minWindowSofar = text.substring(frontIndex, backIndex+1);
                }

                char frontIndexChar = textChars[frontIndex];

                //is it possible to advance front index?
                //we are sure that before advancing, the front index is a pattern char, and the back index is a pattern char too
                //and they are the same pattern chars.
                if (frontIndex != backIndex && cha == frontIndexChar && patternCharHasFound.get(frontIndexChar) > patternCharNeeded.get(frontIndexChar))
                {
                    //advance front index
                    //when on this char, patternCharHasFound > patternCharTotal
                    //or this char is completely not a pattern char
                    while(patternCharNeeded.get(frontIndexChar) == null || patternCharHasFound.get(frontIndexChar) > patternCharNeeded.get(frontIndexChar))
                    {
                        //if the frontIndexChar is a pattern char, we decrement its hasFound map's count
                        //if the frontIndexChar is not a pattern char, we just advance front index
                        if (patternCharNeeded.get(frontIndexChar) != null)
                        {
                            int newfreq = patternCharHasFound.get(frontIndexChar)-1;
                            patternCharHasFound.put(frontIndexChar, newfreq);
                        }

                        //advance front index
                        //look for the next char at incremented frontIndex
                        frontIndex++;
                        frontIndexChar = textChars[frontIndex];
                    }

                    //at the end of the front pointer advancing
                    //we may get a new min window
                    hasAllPatternChars = compareTotalWithHashFound(patternCharNeeded, patternCharHasFound);
                    if (hasAllPatternChars)
                    {
                        //found a new window, is it the min window so far?
                        if (backIndex-frontIndex+1 < minWindowSofar.length())
                        {
                            minWindowSofar = text.substring(frontIndex, backIndex+1);
                        }
                    }
                }

            }
        }
        else
        {
            continue;
        }

    }

    return minWindowSofar;
}

Answer 8

public String minWindow(String S, String T) {
    if(S == null || T == null) return null;
    int[] t = new int[256];                    //chars in T
    int[] s = new int[256];                    //chars found in S between ori and r
    String rl = "";
    for(int i = 0; i < T.length(); i++) t[T.charAt(i)]++;
    for(int ori = 0, r = 0, len = 0; r < S.length(); r++){
        if(t[S.charAt(r)] >= ++s[S.charAt(r)]) len++;
        if(len < T.length()) continue;
        while(s[S.charAt(ori)] > t[S.charAt(ori)]) s[S.charAt(ori++)]--;
        if(rl.equals("") || rl.length() > r - ori + 1) rl = S.substring(ori, r + 1);
    }
    return rl;
}

Minimum Window Substring

Follow this question

Welcome to LeetCode

Related questions