Created
July 20, 2023 02:59
-
-
Save jianminchen/15199fd3588d9a77bd910248df89b720 to your computer and use it in GitHub Desktop.
Minimum substring | C# | Warmup practice on July 19, 2023
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 | |
{ | |
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; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment