Leetcode discuss: 76. Minimum Window Substring

 Here is discussion post. 

C# using extra map to help track sliding window

August 14, 2020
76. Minimum Window Substring
Introduction
It is risky to try a new idea for this hard level algorithm. I like to make coding experience normal, instead of memorizing the past practice. I chose to write normal maintenance of hashmap first, instead of focusing on left pointer continuously sliding right while loop as the first thing in my past practice. I chose to use the idea to clone a hashmap for pattern string, but I forgot the while loop and it's hidden case if the loop falls back to outside one.

To make sure the code works and bug free, there are a list of things to check. Although the idea is working fine, I have to learn how to avoid bugs in my first writing.

It is better to write double loops for this sliding window, left pointer needs to slide more than once sometimes. For this use case, it is better to work on a while loop inside outside while loop with condition index < length. It is more explicitly than hidden one, otherwise I need to add index visited hashset to make sure that index position right pointer will not be processed more than once.

Hard level algorithm
This algorithm is a hard level. It is better for me to write down my practice lessons first, and then I will be better to design the solution considering all the edge cases.

I took the advise to solve all easy level algorithms first in 2018, and leave hard level algorithms later. I do believe that there are more opportunities to learn things from easy level algorithms. So I was able to practice more than 200 easy level and medium level algorithms first, and solved near 500 algorithms.

public class Solution {
    /// <summary>
        /// August 14, 2020
        /// The idea is to write a simple solution, using extra space to make calculation easy; 
        /// Make the problem a computer science data structure, avoid calculation if I can. 
        /// </summary>
        /// <param name="source"></param>
        /// <param name="t"></param>
        /// <returns></returns>
        /// "acbd"
        /// "abc"
        public string MinWindow(string source, string pattern)
        {
            if (source == null || source.Length == 0 || pattern == null || pattern.Length == 0)
            {
                return string.Empty; 
            }

            // using slide window technique, the time complexity will be O(N)
            // variables design: slide window two pointers: left, index
            // a hashmap containing all pattern distinct char and it's count
            // copy of a hashmap to track current window's progress
            // O(1) time to check if the slide window containing all distinct chars and required count
            var patternMap = new Dictionary<char, int>();
            var copyPatternMap = new Dictionary<char, int>();
            foreach (var item in pattern)
            {
                if (!patternMap.ContainsKey(item))
                {
                    patternMap.Add(item, 0);
                }

                patternMap[item]++;
            }   // 'a'=1,'b'=1,'c'=1

            foreach (var pair in patternMap)
            {
                copyPatternMap.Add(pair.Key, pair.Value);
            } // 'a'=1,'b'=1,'c'=1

            var length = source.Length;

            var left = 0;
            var index = 0;
            var minLength = length + 1;
            var startMin = -1;
            var map = new Dictionary<char, int>(); 

            //"acbd"
            while (index < length)
            {
                var current = source[index]; // 'a'
                if (!map.ContainsKey(current)) //
                {
                    map.Add(current, 0);
                }

                map[current]++; //'a'=1

                if (copyPatternMap.ContainsKey(current))
                {
                    copyPatternMap[current]--;
                    if (copyPatternMap[current] == 0)
                    {
                        copyPatternMap.Remove(current);
                    }
                }

                // Find all distinct chars and minimum number for each char
                while (copyPatternMap.Count == 0)
                {
                    var currentWindow = index - left + 1;
                    if (currentWindow < minLength)
                    {
                        minLength = currentWindow;
                        startMin  = left;
                    }

                    // move left point by one
                    var leftChar = source[left];

                    // remove from map
                    map[leftChar]--;
                    var leftCount = map[leftChar];
                    if (map[leftChar] == 0)
                    {
                        map.Remove(leftChar);
                    }

                    // determine if leftChar should be added to copyPatternMap
                    // 
                    var needToAdd = patternMap.ContainsKey(leftChar) &&
                                    leftCount < patternMap[leftChar];
                    if (needToAdd)
                    {
                        if (!copyPatternMap.ContainsKey(leftChar))
                        {
                            copyPatternMap.Add(leftChar, 0);
                        }

                        copyPatternMap[leftChar]++;
                    }

                    left++;
                }                
                
                index++;                 
            }

            return minLength > length ? string.Empty : source.Substring(startMin, minLength); 
        }
}