5
\$\begingroup\$

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;
            }
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm just learning computer science atm and love algorithms and efficiency. Can I ask what is meant by "almost linear complexity"? \$\endgroup\$ – theonlygusti Sep 29 '17 at 14:50
  • \$\begingroup\$ The sliding window has two pointers, left pointer and current index. In terms of left pointer, it will at most visit all characters in the source string at most once, and index pointer will visit all character in the source string once. Even though the outside is for loop, there is while loop inside for loop, but the time complexity is O(n) where n is the source string length. If dictionary is not overloaded, then the time complexity will go up to O(nm), n is the source string length, m is the search string length. \$\endgroup\$ – Jianmin Chen Sep 29 '17 at 14:54
  • 1
    \$\begingroup\$ @theonlygusti If the author is against your edits, stop editing. \$\endgroup\$ – Mast Sep 30 '17 at 17:53
  • 1
    \$\begingroup\$ @Mast the author is wrong. Why can't we edit typos/inaccuracies out of titles? \$\endgroup\$ – theonlygusti Sep 30 '17 at 17:54
  • 1
    \$\begingroup\$ @theonlygusti It looked like the author disagreed with your finding of inaccuracy. To prevent an edit war, at the end of the day, it's his call unless there's something blatant going on. This doesn't qualify as such. \$\endgroup\$ – Mast Sep 30 '17 at 18:11
7
\$\begingroup\$

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;
\$\endgroup\$
  • 1
    \$\begingroup\$ I am surprised to know that you are so good at c#. I like to ask you about your comment about public method return exception, why private no need to throw exception? \$\endgroup\$ – Jianmin Chen Sep 29 '17 at 7:56
  • 3
    \$\begingroup\$ @JianminChen It is redundant to check arguments in private API because you should take care about their validity in the code that is calling the method. Obviously you know how to call your private methods in your code and what arguments should be passed to them. So before to call any private method you check if the method can be called. But you don't know how your public API will be used by a user so you should say if something went wrong. Exception is the native way to do that. \$\endgroup\$ – Maxim Sep 29 '17 at 8:32
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I like to answer your review on var findMatch = (needChars == 0); Based on pluralsight.com clean code course teaching example: Assign Booleans Implicitly with Magic Numbers, if(age > 21) is categorized as Dirty way, whereas Clean way is to write multiple lines: ----- const int legalDrinkingAge = 21------------------------------------------- ------------- if(age > legalDrinkingAge) ----------------------------------------- -------------- { --------------------------- ------------- } --------- \$\endgroup\$ – Jianmin Chen Sep 29 '17 at 6:42
  • \$\begingroup\$ Jianmin, not sure that's applicable here. The issue in your example is the use of a "magic" number, 21. Assign it to a constant and give it a name. In this case we're checking equality with 0. 0 ,1, and 2 are generally not considered "magic" numbers. \$\endgroup\$ – JimB Sep 29 '17 at 6:52
  • 1
    \$\begingroup\$ How about the Principle: Favor expressive code over comments? code with comment: if( needChars == 0) // find a match, whereas expressive code, self-documented code, var findMatch = (needChars == 0). \$\endgroup\$ – Jianmin Chen Sep 29 '17 at 6:59
  • 1
    \$\begingroup\$ @JianminChen although the name 'findMatch' isn't perfect, it's definitely better to use the helper variable that explains the condition so this review won't get my vote for advising to use a plain magic 'if' \$\endgroup\$ – t3chb0t Sep 29 '17 at 7:01
  • 1
    \$\begingroup\$ @t3chb0t, I wrote a blog to document my notes from pluralsight.com clean code course. The blog is juliachencoding.blogspot.ca/2017/07/…. I practice the coding style in mock interview, express the intent, the code looks like verbose, but my speed of coding is improved, less error-prone, easy to do white board testing. \$\endgroup\$ – Jianmin Chen Sep 29 '17 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.