Skip to content

Instantly share code, notes, and snippets.

@jianminchen

jianminchen/Leetcode76_smallestSubstring_RemoveCharNotInArray.cs

Created September 26, 2017 21:58
Download ZIP

Revisions

  1. jianminchen created this gist Sep 26, 2017.
    131 changes: 131 additions & 0 deletions Leetcode76_smallestSubstring_RemoveCharNotInArray.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,131 @@
    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;
    }
    }
    }
    }