Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Get shortest unique substring - code review on the webpage: https://codereview.stackexchange.com/a/176779/123986
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace substring_practice
{
class Program
{
static void Main(string[] args)
{
var testResult = GetShortestUniqueSubstring(new char[] { 'a', 'b', 'c' }, "aefbcgaxy");
Debug.Assert(testResult.CompareTo("bcga") == 0);
}
/// <summary>
/// Oct. 25, 2017
/// code is reviewed on this webpage:
/// https://codereview.stackexchange.com/questions/176769/find-the-smallest-substring-that-contains-some-given-subset-of-characters
/// </summary>
/// <param name="search"></param>
/// <param name="source"></param>
/// <returns></returns>
public static string GetShortestUniqueSubstring(char[] search, string source)
{
if (search == null || search.Length == 0)
{
throw new ArgumentException("Search collection is null or empty.", "Search argument"); // code review 1
}
// assume that search string is not empty
if (string.IsNullOrEmpty(source))
{
throw new ArgumentException("Source string in null or empty", "Source argument"); // code review 2
}
// put unique chars in search string to the dictionary
var map = search.ToDictionary(c => c, c => 1); // code review 3
var needChars = search.Length; // 'xyz' - 3, var match = needChars == 0
// iterate the string and find match, and also keep track of minimum
var left = 0;
var length = source.Length;
var smallestLength = length + 1;
var smallestSubstring = "";
for (int index = 0; index < length; index++)
{
var visit = source[index];
//TryGetValue method to avoid double search of the value by key.
int count; // code review
var inMap = map.TryGetValue(visit, out count); // code review 4
var needOne = inMap && count > 0;
if (inMap)
{
map[visit]--;
}
if (needOne)
{
needChars--;
}
var findMatch = needChars == 0;
if (!findMatch)
{
continue;
}
// move left point forward - while loop
while (left <= index && (!map.ContainsKey(source[left]) || (map[source[left]] < 0))) // code review 5
{
var removeChar = source[left];
// update the variable needChars
if (map.ContainsKey(source[left]))
{
map[removeChar]++;
}
left++;
}
var currentLength = index - left + 1;
var findSmallerOne = currentLength < smallestLength;
if (findSmallerOne)
{
smallestLength = currentLength;
smallestSubstring = source.Substring(left, currentLength);
needChars++;
map[source[left]]++;
left = left + 1;
}
}
// edge case
return smallestLength == length + 1 // code review 6
? string.Empty
: smallestSubstring;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment