Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created July 20, 2023 17:44
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/a5f16ef66c4ef20022fd2291063e55a9 to your computer and use it in GitHub Desktop.
Save jianminchen/a5f16ef66c4ef20022fd2291063e55a9 to your computer and use it in GitHub Desktop.
C# | Find minimum substring given unique characters
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
{
/// <summary>
/// Understand importance to test the code against all kinds of bugs
/// TLE, index-out-of-range, and all other possible issues
/// </summary>
/// <param name="args"></param>
static void Main(string[] args)
{
// aefbc ->efbcga -> bcga - last one is shortest one
var testResult = GetShortestUniqueSubstring(new char[] { 'a', 'b', 'c' }, "aefbcgaxy");
Debug.Assert(testResult.CompareTo("bcga") == 0);
// Code testing
// Add code to test boundary of array - variable left
// understand map value
// "aaa", map['a'] = -2, extra two 'a'
}
/// <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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment