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 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.