Algorithmic Efficiency: GetShortestUniqueSubstring implementation

Question

I came upon this Youtube video and the problem they discussed piqued my interest, so I decided to take a stab at it. Below is the question:

Given an array of unique characters arr and a string str, implement a function, getShortestUniqueSubstring that finds the smallest substring of str containing all the characters in arr. Return "" (empty string) if such a substring doesn't exist.

Come up with an asymptotically optimal solution and analyze the time and space complexities.

Example:

input: arr = ['x','y','z'], str = "xyyzyzyx"`

output: "zyx"`

Constraints:

• [time limit] 5000ms

• [input] array.character arr

  • 1 <= arr.Length <= 30

• [input] string str

  • 1 <= str.Length <= 500

Below is my implementation (in C#):

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        char[] arr = new char[] {'x','y','z'};
        string str = "xyyzyzyx"; 
        Console.WriteLine(GetShortestUniqueSubstring(arr, str));
        
        char[] arr2 = new char[] {'a','b','c', 'd'};
        string str2 = "bbacabdaccdabad"; 
        Console.WriteLine(GetShortestUniqueSubstring(arr2, str2));
    }
    
    public static string GetShortestUniqueSubstring(char[] chars, string str)
    {
        int expectedAsciiSum = 0;  
        Dictionary<char, int> charAndCodeDict = new Dictionary<char, int>();
        for(int i=0; i < chars.Length; i++) {
            char c = chars[i];
            int asciiCode = (int)c;
            expectedAsciiSum+= asciiCode;
            
            charAndCodeDict.Add(c, asciiCode);
        }
        
        int asciiSum=0;
        string result="";  
        foreach(char c in str) 
        {   
            if (charAndCodeDict.TryGetValue(c, out int currentCode)){
                charAndCodeDict.Remove(c); 
                asciiSum+=currentCode;
                result=c+result;
                    
                if(asciiSum == expectedAsciiSum){
                    return result;
                }
            }
        }
        
        return result;
    }
}

You will notice that I have omitted some sanity check(s) and error handling (e.g. checking if an key already exists in charAndCodeDict before adding), because in this context, I am strictly adhering to the constraints listed in the question. In a production environment, I would obviously add the appropriate checks and/or throw Exceptions when needed.

Now, I am no computer scientist, but it looks to me like the time complexity is roughly O(n+m) where n == number of characters in arr and m == the number characters in str. Lookups to any dictionary are completed in constant time (O(1)), so that shouldn't impact speed, although, the memory allocation and building of it would.

Is there anything that can be done to make my implementation more efficient? Aside from that, if there is a more efficient way of doing this that takes a completely different approach, please do let me know.

Answer 1

Algorithm issue 1

Your code is not correct. You're not getting the substrings. You're getting a list of the first occurrence of each character, and pasting those values together (in reverse order, for some reason) as if they were a substring.

Try the following test case:

char[] arr1 = new char[] {'x','y','z'};
string str1 = "zzyyxxzy"; 
Console.WriteLine(GetShortestUniqueSubstring(arr1, str1));

I'm going to refer to this test case repeatedly.

The found substring should be zzyyx[xzy], but your result is xyz.

Notice what happens when I change str from [zzyy]xxzy to [yyzz]xxzy. The result is now xzy. That doesn't make sense. I changed something that is not part of the substring that should (allegedly) be returned, yet the returned (alleged) substring is somehow different now. What gives?

What you missed here is that substrings are contiguous. They do not allow breaks or gaps.

If you follow the code example I gave, you will see that the xyz result is based off of input string [z]z[y]y[x]xzy, and you concatenate these occurrences in reverse order.

An easy way to troubleshoot this is to log the index of every "hit" you find. I adjusted your code to track this:

int asciiSum=0;
string result="";  
int counter = 0;                           // HERE
foreach(char c in str) 
{   
    counter++;                         // HERE

    if (charAndCodeDict.TryGetValue(c, out int currentCode)){
        charAndCodeDict.Remove(c); 
        asciiSum+=currentCode;
        result=c+result;
        
        // HERE
        Console.WriteLine($"Hit: Character '{c}' in position {counter}");
                
        if(asciiSum == expectedAsciiSum){
            return result;
        }
    }
}

For the input example I provided:

Hit: Character 'z' in position 1
Hit: Character 'y' in position 3
Hit: Character 'x' in position 5
xyz

The result would only be a substring if all logged positions were sequential, which they are not.

I'll leave the exercise on how to fix this up to you. Use the logging I added here as a quick way to confirm that your code works as expected.

---

Algorithm issue 2

Your code only works when chars contains no duplicate characters, but that's an unnecessary constraint. The question does not exclude the possibility of duplicates, and they should factor into your algorithm. E.g. new char[] {'x','y','z', 'z' } should yield a four-or-more-letter substring with 1 x, 1 y and 2 z characters (and any additional characters if part of the shortest available substring).

---

LINQ

LINQ helps clean up code that deals with iterations, and makes it far more readable.

For example, your dictionary-building logic can be replaced with:

var charAndCodeDict = chars
                        .Distinct()
                        .ToDictionary(
                            c => c,       // Key = the character itself 
                            c => (int)c   // Value = the character as an int
                         );

int expectedAsciiSum = chars.Sum(c => (int)c);

I added extra line breaks to make it easier to parse the methods and their arguments.

Explanation:

• LINQ operates on collections, but string inherently gets treated as a char[] so it does count as a collection.
• Distinct removes duplicates, which is important to avoid conflicts when generating a dictionary (colliding keys).
• ToDictionary needs two parameters: how to select the key, and how to select the value. This logic is applied to each element in the input array, and ToDictionary then returns the compiled dictionary from all these cases.
• Sum adds all of the selected values together and returns, well, the sum.

You might find it complex because you're not used to LINQ, but once you know what each of the LINQ methods do (there's about 10 commonly used ones), it really helps trim down the character count and ease the readability.

---

String concatenation

result=c+result;

+ is not a good way to concatenate strings. It works but it becomes horribly inefficient when used repeatedly.

There are better ways to concatenate strings. Especially when dealing with more than one or two + concatenations, you should really look at the others.

In this case, I would recommend either using a StringBuilder, or simply tracking a char[] and only joining it into a string at the end of the method (not during each iteration for every character).

---

Submethods

Your GetShortestUniqueSubstring has two distinct sections: generating a dictionary, and processing the input string. These are two separate things and could/should have been separated into their own method.

Note that this applies because your dictionary-building logic is more than a simple one liner. If you used my LINQ example, this point would be rendered moot, unless there is a reusability argument that still suggests putting this dictionary-building logic into a method of its own.

---

Overall syntax

Overall, your syntax is good. Relatively clear naming (maybe a bit too lengthy at times, but it's better than being too terse).

The only thing that stands out are the egyptian brackets you're using, which is not idiomatic in C#. In C#, the opening bracket goes on a new line.

Answer 2

I ended up getting really busy, so I wasn't able to respond as quickly as I had hoped. Saying that, @flater pointed out that I wasn't generating actual substrings, which is true, and I attribute that to my misinterpretation of the question. Realizing this prompted me to re-write the algorithm entirely (which I almost believe is worth asking a separate question about, but I decided to just add it as an answer), which I will outline below:

using System;
using System.Collections.Generic;
using System.Text;

namespace AlgoTest
{
    public class Program
    {
        public static void Main()
        {
            //Base Case test
            char[] arr = new char[] { 'x', 'y', 'z' };
            string str = "xyyzyzyx";
            Console.WriteLine(GetShortestUniqueSubstring(arr, str));

            //Longer String Test
            char[] arr2 = new char[] { 'a', 'b', 'c', 'd' };
            string str2 = "bbacabdaccdabad";
            Console.WriteLine(GetShortestUniqueSubstring(arr2, str2));

            //Duplicate chars test
            char[] arr3 = new char[] { 'd', 'a', 'c', 'c' };
            Console.WriteLine(GetShortestUniqueSubstring(arr3, str2));

            //Duplicate chars that CANNOT be found in str2
            char[] arr4 = new char[] { 'b', 'b', 'a', 'd', 'd' };
            Console.WriteLine(GetShortestUniqueSubstring(arr4, str2));

            Console.ReadKey();
        }

        public static string GetShortestUniqueSubstring(char[] chars, string str)
        {
            int charsLen = chars.Length;

            int expectedAsciiSum = 0;
            IDictionary<char, int> charAndCodeDict = new Dictionary<char, int>();
            for (int i = 0; i < charsLen; i++)
            {
                char c = chars[i];
                int asciiCode = (int)c;
                expectedAsciiSum += asciiCode;

                if (!charAndCodeDict.ContainsKey(c))
                {
                    charAndCodeDict.Add(c, asciiCode);
                }
            }

            return GetShortestSubstring(charsLen, expectedAsciiSum, charAndCodeDict, str);
        }

        private static string GetShortestSubstring(int maxCharLen, int expectedAsciiSum, IDictionary<char, int> charAndCodeDict, string str, int startPos = 0)
        {
            StringBuilder builder = new StringBuilder();

            int strLen = str.Length;
            int totalSearchChars = startPos + strLen;

            int counter = 0;
            int asciiSum = 0;
            for (int i = startPos; i < strLen; i++)
            {
                counter++;

                /*
                if the distance between the totalSearchChars and the
                current position in the string is less than the maxCharLen,
                then the total number of remaining characters left to check 
                (i.e. i to (strLen - 1)) cannot be a substring
                */
                if ((totalSearchChars - i) >= maxCharLen)
                {
                    char c = str[i];

                    /*
                    In some cases, the 'asciiSum' of several characters could amount
                    to the 'expectedAsciiSum', even if some of the characters that make
                    up the 'asciiSum' are not found in the original char array,
                    so we need to that check the current char (i.e. c) exists first
                    */
                    if (charAndCodeDict.TryGetValue(c, out int currentCode))
                    {
                        if (counter <= maxCharLen)
                        {
                            asciiSum += currentCode;
                            builder.Append(c);

                            if (counter == maxCharLen)
                            {
                                if (asciiSum == expectedAsciiSum)
                                {
                                    return builder.ToString();
                                }

                                counter = 0;
                                asciiSum = 0;
                                builder.Clear(); 
                            }
                        }
                    }
                    else
                    {
                        counter = 0;
                        asciiSum = 0;
                        builder.Clear();
                    }
                }
                else
                {
                    return GetShortestSubstring(maxCharLen, expectedAsciiSum, charAndCodeDict, str, startPos + 1);
                }
            }

            return builder.ToString();
        }

    }
}

You will notice that I split the search for the actual sub string into a separate recursive function called GetShortestSubstring. This was done to support the separation of concerns as well as to allow recursion. Essentailly, GetShortestSubstring does the follolwing:

1. Loops through the str starting from the leftmost position (i.e. startPos) and, counting each iteration.
2. Checks if the distance between the totalSearchChars and the current position in the string (i.e. i), is >= the total number of characters in the original arr (i.e. maxCharLen). If not, then total number of characters left to check, will be less than the maxCharLen, which could never match a substring derived from the arr, so we need to start over searching from the startPos + 1 using recursion.
3. Looks in the charAndCodeDict to see if the current character (i.e. c) matches any of the ones found in the original arr and returns its ascii code. If c is not found, then reset the counter, asciiSum, and builder.
4. Checks that the current iteration count (i.e. counter) is < the maxCharLen and if so increments the asciiSum and appends c to the builder.
5. If counter == maxCharLen then check to see if the asciiSum == expectedAsciiSum and if so return the underlying sting from the builder, otherwise reset the counter, asciiSum, and builder, and continue the loop.

The problem actually does explicitly state that arr should not contain duplicates in the first line:

Given an array of unique characters arr

However, I do agree this is an unnecessary constraint. As for comments regarding LINQ (which I am very familiar with), I disagree in this context. I believe than an algorithm should be reproducible in virtually any programming language, and I prefer to keep the implementation as explicit (and language/platform agnostic) as possible. Additionally, (and in this context) LINQ would merely be syntatic sugar in place of standard for loops, which are faster (albeit more verbose) anyway. Speaking of speed, I also agree that concatenations performed in a loop are better done with an instance of a StringBuilder (especially when the arr is sufficiently large), regardless of the overhead of encountered upon instantiation. Notice also that I changed the placing of my brackets to conform to more idiomatic C# syntax. I do not normally use Egyption Brackets, but I used them in my question to shorten the code block to prevent viewers from having to scroll unnecessarily. The one idiomatically placed bracket in the second foreach is evidence of an oversight in my futile attempt to reduce the size of the code block.

Even with the re-write, I am still not convinced that this is the most efficient implementation....and it also doesn't look as pretty (specifically the variable resets). Any suggestions to make this more efficient (and "prettier" short of using LINQ) are welcome.