Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save jianminchen/a4423347fe699468e65855d217d2a539 to your computer and use it in GitHub Desktop.
Save jianminchen/a4423347fe699468e65855d217d2a539 to your computer and use it in GitHub Desktop.
Leetcode 76 - smallest substring - remove char not in the unique char array. The algorithm passes all test cases.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace substring_practice
{
// []'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
class Program
{
static void Main(string[] args)
{
var testResult = GetShortestUniqueSubstring(new char[] { 'A', 'B', 'C' }, "ADOBECBANCD");
Debug.Assert(testResult.CompareTo("BANC") == 0);
}
/// <summary>
/// 9/26/2017
/// Work on left pointer while loop issue
/// test case: xxxyz, unqiue array 'x', 'y','z'
///
/// </summary>
/// <param name="arr"></param>
/// <param name="str"></param>
/// <returns></returns>
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; //
var smallestSubstring = "";
for (int index = 0; index < length; index++) //
{
var visit = str[index];
// x - 1
var inMap = map.ContainsKey(visit);
var needOne = inMap && map[visit] > 0; // add checking contains
if (inMap)
{
map[visit]--;
}
if (needOne)
{
needChars--; // take x off
}
var findMatch = needChars == 0;
if (!findMatch)
{
continue;
}
// move left point forward - while loop
while (left <= index && (!map.ContainsKey(str[left]) || (map.ContainsKey(str[left]) && map[str[left]] < 0)))
{
var removeChar = str[left];
// update the variable needChars xx -1
if(map.ContainsKey(str[left]))
{
map[removeChar]++;
}
left++;
}
var currentLength = index - left + 1;
var findSmallerOne = currentLength < smallestLength;
if (findSmallerOne)
{
smallestLength = currentLength;
smallestSubstring = str.Substring(left, currentLength);
needChars++;
map[str[left]]++;
left = left + 1;
}
}
// edge case
if (smallestLength == length + 1)
{
return "";
}
else
{
return smallestSubstring;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment