leetcode: Minimum Window Substring

Problem Description:

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,
T = "ABC"

Minimum window is "BANC".

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.

Solution and Precautions:

Use hash table to check if a character is in T or not. And use two pointers indicating the window in S, expand the right pointer until the window contains all the characters in T, and move the left pointer to right as far as possible, get the minimum window candidate, if this window is shorter, then update the global window. Since both the left and right window will check the character exactly once, the time is O(2N).

Tips and Divergent thinking:

Once can check this post in leetcode for reference: http://leetcode.com/2010/11/finding-minimum-window-in-s-which.html

Written on June 5, 2013