Created
September 26, 2017 21:58
-
-
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.
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 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