Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode 76 - find smallest substring containing all characters in an array with distinct character. Need to work on the left point while loop.
using System;
class Solution
{
// []'x','y','z'] - substring containing all characters
// find smallest -> minimum length
//linear scan string -> O(n), visit char once
// left point -> current point ->
// index = 0
// x -> hashmap -> Dictinary<char, int> 'x', 1 , 'y' 1, 'z' 1
// x -> 'x' 1 - 1 -> 0 , no need
// left 0 ->
// y -> 'y' 1 -1 -> 0 -> variable to help to check if > 0
// y -> 'y' 0 - 1 -> -1
// z -> 'z' 1 - 1 -> 0 find word -> left 0, index = 3, "xyyz", length = 4, minimum
// left point -> x -> +1, need one x , value 1 > 0
// go back step 18 or 19
public static string GetShortestUniqueSubstring(char[] arr, string str)
{
// your code goes here
if(arr == null || arr.Length == 0)
{
return "";
}
// assume that arr is not empty
if(str == null || str.Length == 0)
{
return "";
}
// put arr to the dictionary
var map = new Dictionary<char, int>();
foreach(var item in arr)
{
map.Add(item, 1);
}
var needChars = arr.Length; // 'xyz' - 3, var match = needChars == 0
// iterate the string and find match, and also keep track of minimum
var left = 0;
var length = str.Length;
var smallestLength = length + 1; // length + 1
var smallestSubstring = "";
//for(int index = 0; index < length; index++ )
while()
{
var visit = str[index];
// x - 1
var needOne = map[visit] > 0;
map[visit] --;
if(needOne)
{
needChars --; // take x off
}
var findMatch = needChars == 0;
if(findMatch)
{
var curentLength = index - left + 1;
var findSmallerOne = currentLength < smallestLength;
if(findSmallerOne)
{
smallestLength = curentLength;
smallestSubstring = str.Substring(left, index - left + 1);
}
// move left point forward
var removeChar = str[left];
// update the variable needChars xx -1
var needIncrement = map[removeChar] == 0;
if(needIncrement) // do a loop - xxxxyz -> 6 -> xyz, do a loop to remove all 3 x -> xyz
{
needChars ++;
}
map[removeChar] ++; // line 16
left ++;
//
}
}
// edge case
if(smallestLength == length + 1)
{
return "";
}
else
{
return smallestSubstring;
}
}
static void Main(string[] args)
{
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment