Leetcode 76 - smallest substring - remove char not in the unique char array. The algorithm passes all test cases.

Leetcode76_smallestSubstring_RemoveCharNotInArray.cs

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

namespace substring_practice
{
    // []'x','y','z'] - substring containing all characters
    // find smallest -> minimum length 
    //linear scan string -> O(n), visit char once 
    // left point -> current point -> 
    // index = 0 
    // x -> hashmap -> Dictinary<char, int> 'x', 1 , 'y' 1, 'z' 1 
    // x -> 'x' 1 - 1 -> 0 , no need 
    // left 0 -> 
    // y -> 'y' 1 -1 -> 0 -> variable to help to check if > 0 
    // y -> 'y' 0 - 1 -> -1 
    // z -> 'z' 1 - 1 -> 0  find word -> left 0, index = 3, "xyyz", length = 4, minimum
    // left point -> x -> +1, need one x , value 1 > 0 
    // go back step 18 or 19 
    class Program
    {
        static void Main(string[] args)
        {
            var testResult = GetShortestUniqueSubstring(new char[] { 'A', 'B', 'C' }, "ADOBECBANCD"); 
            Debug.Assert(testResult.CompareTo("BANC") == 0); 
        }

        /// <summary>
        /// 9/26/2017
        /// Work on left pointer while loop issue
        /// test case: xxxyz, unqiue array 'x', 'y','z'
        /// 
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="str"></param>
        /// <returns></returns>        
        public static string GetShortestUniqueSubstring(char[] arr, string str)
        {
            // your code goes here
            if (arr == null || arr.Length == 0)
            {
                return "";
            }

            // assume that arr is not empty
            if (str == null || str.Length == 0)
            {
                return "";
            }

            // put arr to the dictionary

            var map = new Dictionary<char, int>();
            foreach (var item in arr)
            {
                map.Add(item, 1);
            }

            var needChars = arr.Length; // 'xyz' - 3, var match = needChars == 0 
            // iterate the string and find match, and also keep track of minimum 
            var left = 0;
            var length = str.Length;

            var smallestLength = length + 1;  //  
            var smallestSubstring = "";

            for (int index = 0; index < length; index++)   //  
            {
                var visit = str[index];

                // x - 1 
                var inMap = map.ContainsKey(visit);
                var needOne = inMap && map[visit] > 0; // add checking contains
                if (inMap)
                {
                    map[visit]--;
                }

                if (needOne)
                {
                    needChars--; // take x off 
                }

                var findMatch = needChars == 0;
                if (!findMatch)
                {
                     continue;
                }

                // move left point forward - while loop                
                while (left <= index && (!map.ContainsKey(str[left]) || (map.ContainsKey(str[left]) && map[str[left]] < 0)))
                {                    
                    var removeChar = str[left];

                    // update the variable needChars xx -1                     
                    if(map.ContainsKey(str[left]))
                    {
                        map[removeChar]++; 
                    }

                    left++;
                }

                var currentLength = index - left + 1;
                var findSmallerOne = currentLength < smallestLength;
                if (findSmallerOne)
                {
                    smallestLength = currentLength;
                    smallestSubstring = str.Substring(left, currentLength);

                    needChars++;
                    map[str[left]]++; 
                    left = left + 1;
                }
            }

            // edge case
            if (smallestLength == length + 1)
            {
                return "";
            }
            else
            {
                return smallestSubstring;
            }
        }
    }          
}