[Uber] Minimum Window Substring

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

Example:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Approach: 

1. First check if the length of string is less than the length of the given pattern, if yes then return empty string.
2. Store the occurrence of characters of the given pattern in a hash.
3. Start matching the characters of pattern with the characters of string i.e. increment count if a character matches.
4. Check if (count == length of pattern ) this means a window is found.
5. If such window found, try to minimize it by removing extra characters from the beginning of the current window.
6. Update minWindowLength.
7. Return the minimum length window.

Implementation in C#:

        public string MinWindow(string s, string t)

        {

            if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t))

            {

                return "";

            }

            if (s.Length < t.Length)

            {

                return "";

            }

            Dictionary<int, int> hashT = new Dictionary<int, int>();

            Dictionary<int, int> hashS = new Dictionary<int, int>();

            for (int i = 0; i < t.Length; ++i)

            {

                if (!hashT.ContainsKey(t[i]))

                {

                    hashT.Add(t[i], 0);

                }

                ++hashT[t[i]];

            }

            int start = 0, startIndex = -1, minWinLength = int.MaxValue, count = 0;

            for (int i = 0; i < s.Length; ++i)

            {

                if (!hashS.ContainsKey(s[i]))

                {

                    hashS.Add(s[i], 0);

                }

                ++hashS[s[i]];

                if (hashT.ContainsKey(s[i]) && hashS[s[i]] <=  hashT[s[i]])

                {

                    ++count;

                }

                // All chars found

                if (count == t.Length)

                {

                    while(!hashT.ContainsKey(s[start]) || hashS[s[start]] > hashT[s[start]])

                    {

                       --hashS[s[start]];

                        ++start;

                    }

                    int currLen = i - start + 1;

                    if (currLen < minWinLength)

                    {

                        minWinLength = currLen;

                        startIndex = start;

                    }

                }

            }

            if (startIndex == -1)

            {

                return "";

            }

            return s.Substring(startIndex, minWinLength);

        }

Complexity: O(n)