Problem statement:

Give a string as a "source" string, find the smallest substring of source such that it contains all characters in "search" string which contains the unique characters.

Given a test case for easy to come out your design of the algorithm, the source string contains characters not in search string, the smallest substring contains the character not in the search string as well. For example, search string ['a','b','c'], source string "aefbcgaxy", the shortest string is "bcga".

My analysis of algorithm

It is my favorite algorithm to practice two pointer techniques and also use slide window to reduce the time complexity to almost linear complexity by overloading the count value of unique characters.

For example, search string ['a','b','c'] can map to a C# dictionary with 'a' as key with value 1, 'b' with 1, 'c' with 1. The value of key 'a' can also be used to track how many 'a' are consumed when iterating the search string from left to right. Key 'a' with value 0 means that no 'a' is needed in sliding window, -1 means that the substring in sliding window has extra one 'a'.

Here is my C# code. I have practiced string search algorithm since January 2015. I am still learning how to write an efficient solution in terms of time complexity, also apply the principle I learned a few months ago called TED Principle (Terse, Express the intent, Do one thing) through pluralsight.com course clean code: write code for humans. Please help me review my code and help me to write clean code.

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

namespace substring_practice
{

    class Program
    {
        static void Main(string[] args)
        {
            var testResult = GetShortestUniqueSubstring(new char[] { 'A', 'B', 'C' }, "ADOBECBANCD");
            Debug.Assert(testResult.CompareTo("BANC") == 0);
        }
              
        public static string GetShortestUniqueSubstring(char[] search, string source)
        {
            // your code goes here
            if (search == null || search.Length == 0)
            {
                return "";
            }

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

            // put arr to the dictionary
            var map = new Dictionary<char, int>();
            foreach (var item in search)
            {
                map.Add(item, 1);
            }

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

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

            for (int index = 0; index < length; index++)   //  
            {
                var visit = source[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(source[left]) || (map.ContainsKey(source[left]) && map[source[left]] < 0)))
                {
                    var removeChar = source[left];

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

                    left++;
                }

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

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

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