76. Minimum Window Substring

Here is my discussion post.

It is challenging task to design a sliding window which has intelligent way to keep count all chars in sliding window no matter whether the char is in pattern string t. I choose to write a solution based on the video shared by Daniel Su.

Small case stduy

S = "ACBA", t ="AB",

There is step by step explanation in the above video using the above test case. I also like to explain the design.

About right pointer in sliding window
if the char on position of right pointer has bank value bigger than 0, then the char is counted towards to be one of chars in pattern t. Variable count decrement one, no matter right char is in pattern string t, bank count will always decrement one.

About left pointer in sliding window
It is similar idea to hanlde left pointer. The argument is if bank[leftChar] > 0, then one of chars in pattern string s is removed from sliding window, count variable should decrement one.

Why it is hard level algorithm?

1. Fact 1:

work on test case
s = "ABBB", t = "ABB", the pattern string may have duplicate chars. So the sliding window should contain all unique chars and also its count for each char. The minimum sliding window should contain all unique chars in pattern string, and also keep at least same count for each char as well.

2. Fact 2:
   How to determine if the string in sliding window contains (denoted as sw) all chars in pattern string s?

counting sort all chars in sw and s, and then compare each char and its count. This takes O(k) time, k is distinct chars in pattern string t. It can be O(1) time instead.

How to design the technique to make it O(1)?

For example, S = "ACBA", t ="AB".
Char C's bank value from 0 to -1, and then left pointer moves away index = 1, go back to 0. Since C is not in string t, C's bank value will never go beyond 0.

First it is the design in template to document all chars in sliding window using bank array. Even the characters not in pattern string t will be recorded, for characters in pattern string t will be recorded using bank array, since pattern string may have more than one copy of the same char, how to tell which copy of char goes to count of pattern string t.

Next count variable is introduce to keep "the sliding window contains all char and it's count in pattern string t" checking O(1) time.

Five minutes to understand count variable design

It is tough job to design count variable. It took me hours to understand when to increment one to count variable, when to decrement one to count variable.

One thing I can do is to show a simple test case. The solution is not difficult to write at all.

s = "AAB", t = "AB",
I think that the above test case first 'A' is visited, bank['A'] = 1, so count variable should be incremented by one. Second 'A' is visited, bank['A'] = 0, so count variable will not be incremented.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _76_minimum_window_substring_optimal
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// July 15, 2019
        /// study code
        /// https://www.youtube.com/watch?v=9odu9ImG9oY
        /// </summary>
        /// <param name="s"></param>
        /// <param name="t"></param>
        /// <returns></returns>
        public string MinWindow(string s, string t)
        {
            if (s == null || s.Length == 0 ||
                t == null || t.Length == 0)
            {
                return "";
            }

            var bank = new int[256];
            
            int left = 0;
            int right = 0;
            int count = 0;

            int min = Int32.MaxValue;
            string minString = "";

            var pLength = t.Length;
            var length = s.Length;

            for (int i = 0; i < pLength; i++)
            {
                bank[t[i]]++;
            }

            while (right < length)
            {   
                var rightChar = s[right];
                right++; // always advance one to next iteration 
                if (bank[rightChar] > 0)
                {
                    count++;
                }

                bank[rightChar]--; // always decrement one no matter char is in pattern t or not                              

                // move left pointer until missing one char from string t
                while (count == pLength)
                {
                    var size = right - left;
                    if (min > size)
                    {
                        min = size;
                        minString = s.Substring(left, right - left);
                    }

                    // shift our window
                    var leftChar = s[left];
                    left++;  // always move left pointer
                    bank[leftChar]++; // always increment one no matter char is in pattern t or not                    

                    if (bank[leftChar] > 0) // that means left char is one of chars in pattern, also count as one
                    {
                        count--;
                    }
                }
            }

            return minString;
        }
    }
}