Created
February 12, 2018 07:12
-
-
Save jianminchen/0ad5969c03fcf1b2ddf285ff604ca976 to your computer and use it in GitHub Desktop.
smaller substring study code
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; | |
class Solution | |
{ | |
public static string GetShortestUniqueSubstring(char[] arr, string str) | |
{ | |
if (arr == null || str == null || arr.Length > str.Length) return ""; | |
int uCount = arr.Length; | |
int n = str.Length; | |
// Count of elements which are present in arr | |
var count = new Dictionary<char, int>(); | |
int i, j; | |
int min = Int32.MaxValue; // window length | |
int start = -1; // answer start position | |
for(i = 0; i < uCount; i++){ | |
count[arr[i]] = 0; | |
} | |
int found = 0; j = 0; | |
for(i = 0; i <= n- uCount; i++) | |
{ | |
// at the end of this loop j should be pointing just at the end of thw windows | |
while (found != uCount && j < n){ | |
if (count.ContainsKey(str[j])){ | |
if (count[str[j]] == 0){ | |
found++; | |
} | |
count[str[j]]++; | |
} | |
j++; | |
} | |
if (found == uCount && (j-i) < min){ // Found a new smaller window | |
min = j-i; | |
start = i; | |
} | |
// If the str[i] | |
if (count.ContainsKey(str[i])){ | |
if (count[str[i]] == 1){ | |
found--; | |
} | |
count[str[i]]--; | |
} | |
} | |
if (start == -1) return ""; | |
return str.Substring(start, min); | |
/* | |
xyyzyzyx | |
i=0 left end of the window | |
j = right end of the window | |
var count = int [256] | |
[i,j] = find all the character of arr | |
start with i = 0 | |
find j till all the characters in arr is covered | |
window - compare it with old window, if it smaller then save it. | |
i = 1; | |
decerment the value count[a[0]]--; it doesn't affect the all covering of element in arr | |
remaining element is less than size of arr | |
*/ | |
} | |
static void Main(string[] args) | |
{ | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment