Created
July 20, 2023 17:44
-
-
Save jianminchen/a5f16ef66c4ef20022fd2291063e55a9 to your computer and use it in GitHub Desktop.
C# | Find minimum substring given unique characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode 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