Find the smallest substring that contains some given subset of characters

Question

Problem statement:

Given a string as a "source" string, find the smallest substring of source such that it contains all characters in "search" string (which contains distinct characters).

For example, for search string ['a','b','c'], source string "aefbcgaxy", the shortest string is "bcga".

My algorithm

In this algorithm, I practiced two-pointer techniques and also used a sliding 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'.

My mistakes

I have practiced string search algorithm since January 2015. But I am still not good at thinking about edge cases. I made a few mistakes in the first few practices, and finally I came out the above test case to cover all edge cases.

I still make those common mistakes. Visit the hashmap without checking the key is existing in the dictionary first. The second one is to consider two cases, either in the dictionary or not in the dictionary. The third one is to maintain the dictionary value by adding one or decreasing one.

TED principle

I am still learning how to write an efficient solution in terms of time complexity, and to 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' }, "aefbcgaxy");
            Debug.Assert(testResult.CompareTo("bcga") == 0);
        }

        public static string GetShortestUniqueSubstring(char[] search, string source)
        {                
            if (search == null || search.Length == 0)
            {
                return "";
            }

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

            // put unique chars in search string 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];

                var inMap = map.ContainsKey(visit);
                var needOne = inMap && map[visit] > 0; 
                if (inMap)
                {
                    map[visit]--;
                }

                if (needOne)
                {
                    needChars--;  
                }

                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                     
                    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;
            }
        }
    }
}

Answer 1

If some arguments of a public method is invalid you should say about it to user. The native way in .NET to say about something is wrong is an exception. So instead of returning some "invalid" value throw an exception:

if (search == null || search.Length == 0)
{
    throw new ArgumentException("Search collection is null or empty.", nameof(search));
}

if (string.IsNullOrEmpty(source))
{
    throw new ArgumentException("Source string is null or empty.", nameof(source));
}

Always use string.IsNullOrEmpty instead of source == null || source.Length == 0.

---

This code

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

can be simplified to

var map = search.ToDictionary(c => c, c => 1);

---

Every time you need to check if a value is presented in a dictionary and if yes then get it, you should use the TryGetValue method to avoid double search of the value by key. So instead of

var inMap = map.ContainsKey(visit);
var needOne = inMap && map[visit] > 0;

you should write

int count;
var inMap = map.TryGetValue(visit, out count);
var needOne = inMap && count > 0;

or using C# 7:

var inMap = map.TryGetValue(visit, out var count);
var needOne = inMap && count > 0;

---

In this condition

while (left <= index && (!map.ContainsKey(source[left]) || (map.ContainsKey(source[left]) && map[source[left]] < 0)))

the map.ContainsKey(source[left]) is redundant since at this moment you already know that it is true because !map.ContainsKey(source[left]) is false. So the condition can be simplified to

while (left <= index && (!map.ContainsKey(source[left]) || map[source[left]] < 0))

or using C# 7 along with TryGetValue:

while (left <= index && (!map.TryGetValue(source[left], out var count) || count < 0))

---

This

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

can be simplified to

return smallestLength == length + 1
    ? string.Empty
    : smallestSubstring;

Answer 2

I like your description and algorithm. I think your code looks pretty clean.

For statements like:

var findMatch = (needChars == 0);

I personally like to add parens (though unnecessary) to highlight the relational expression. I find it aids readability.

However, in this case, I would eliminate findMatch. The code seems obvious without it. Adding the variable just makes me wonder why the variable is there. I'm expecting to see it later. So I would do:

if (needChars > 0)
{
    continue;
}

Same thing with:

var findSmallerOne = currentLength < smallestLength;
if (findSmallerOne)

I think it's more readable simply as:

if (currentLength < smallestLength)

especially since you are then updating smallestLength.

You've got an extra condition here:

while (left <= index && (!map.ContainsKey(source[left]) || (map.ContainsKey(source[left]) && map[source[left]] < 0)))

you don't need to check left <= index as it MUST be <= because we have a match with a non-null string.

Finally, I'd recommend looking at your comments. If the comment is just saying what is obvious in the code, remove it. Comments should help explain something that is (unavoidably) non-obvious. For example, consider these comments... are they really telling us anything non-obvious?

// assume that search string is not empty

// put unique chars in search string to the dictionary

// edge case

I didn't understand this one:

// 'xyz' - 3, var match = needChars == 0

A good comment might be a high-level explanation of your algorithm.

Edit: I did find one algorithmic thing which I would change. With this code:

if (findSmallerOne)
{
    smallestLength = currentLength;
    smallestSubstring = source.Substring(left, currentLength);

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

I would move the needChars part out of the if statement. Like this:

if (findSmallerOne)
{
    smallestLength = currentLength;
    smallestSubstring = source.Substring(left, currentLength);
}

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

You want to make the string incomplete again (so that you can continue searching) regardless if you've found the shortest substring. Maybe you've found a longer substring this time.