Find minimum substring given unique characters

 C# | Sliding window | July 2023 | Test cases | Warm up

jianminchen

774

7

20 hours ago

C#

Intuition

Approach

Complexity

• Time complexity:

O(m + n), m is length of string, n is length of pattern string.

• Space complexity:

Code

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

namespace _76_minimum_window_substring_review
{
    class Program
    {
        static void Main(string[] args)
        {
            var testResult = GetShortestUniqueSubstring(new char[] { 'a', 'b', 'c' }, "aaaefbcgaxy");
            Debug.Assert(testResult.CompareTo("bcga") == 0);
        }

        /// <summary>
        /// code review on July 19, 2023
        /// https://codereview.stackexchange.com/questions/176769/find-the-smallest-substring-that-contains-some-given-subset-of-characters
        /// </summary>
        /// <param name="search"></param>
        /// <param name="source"></param>
        /// <returns></returns>
        public static string GetShortestUniqueSubstring(char[] search, string source)
        {
            if (search == null || search.Length == 0 || string.IsNullOrEmpty(source))
            {
                return "";
            }

            // put unique chars in search string to the dictionary
            var map = new Dictionary<char, int>();
            var set = new HashSet<char>(search);

            foreach (var item in search)
            {
                map.Add(item, 1);
            }           

            // 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 (map.ContainsKey(visit))
                {
                    map[visit]--;                   
                }

                set.Remove(visit);
                
                if (set.Count > 0)
                {
                    continue;
                }

                // move left point forward
                // extra one -> value in hashmap has negative value 
                while (left <= index && (!map.ContainsKey(source[left]) || map[source[left]] < 0))
                {
                    var removeChar = source[left];
                                     
                    if (map.ContainsKey(removeChar))
                    {
                        map[removeChar]++;
                    }

                    left++;
                }

                // added on July 19, 2023 - index-out-of-range concern
                if (left == length)
                {
                    break;
                }

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

                var removed = source[left];
                map[removed]++;
                set.Add(removed);  // match map 

                left = left + 1;                                                               
            }

            return smallestLength == (length + 1) ? "" : smallestSubstring;            
        }
    }
}