- #1
SlurrerOfSpeech
- 141
- 11
characters in a specified amount. I've been working on this for 10+ hours and can't seem to get it right. It passes all the unit tests I've written, but when I use it in the context of the program I'm writing it fails.
The idea is like
ACTAGACC
{ A : 2, C : 1}
------> 4, because smallest substring containing 2 As and 1 C is ACTA.
For some reason, I'm finding this very tricky to write an efficient an elegant solution. The brute force approach (Find all substrings and see which is the smallest that contains the characters) doesn't meet the performance benchmarks that I have.
My code:
The idea is like
ACTAGACC
{ A : 2, C : 1}
------> 4, because smallest substring containing 2 As and 1 C is ACTA.
For some reason, I'm finding this very tricky to write an efficient an elegant solution. The brute force approach (Find all substrings and see which is the smallest that contains the characters) doesn't meet the performance benchmarks that I have.
My code:
Code:
using System;
using System.Collections.Generic;
using System.Linq;
public class MethodTest
{
public Dictionary<char,int> Counter { get; set; }
public string Source { get; set; }
public int ExpectedResult { get; set; }
}
public class Program
{
public static void UnitTests()
{
var tests = new List<MethodTest>() {
new MethodTest() { Source = "ABB", Counter = new Dictionary<char,int>() { { 'B', 1 } }, ExpectedResult = 1 },
new MethodTest() { Source = "ABB", Counter = new Dictionary<char,int>() { { 'A', 1 } }, ExpectedResult = 1 },
new MethodTest() { Source = "A", Counter = new Dictionary<char,int>() { { 'R', 1 } }, ExpectedResult = -1 },
new MethodTest() { Source = "ATTC", Counter = new Dictionary<char,int>() { { 'T', 1 } }, ExpectedResult = 1 },
new MethodTest() { Source = "AAAA", Counter = new Dictionary<char,int>() { { 'A', 3 } }, ExpectedResult = 3 },
new MethodTest() { Source = "AAATTTGC", Counter = new Dictionary<char,int>() { { 'A', 1 }, { 'T', 1 } }, ExpectedResult = 2 },
new MethodTest() { Source = "GAAATAAA", Counter = new Dictionary<char,int>() { {'A', 4 } }, ExpectedResult = 5 }
};
foreach(var test in tests)
{
int result = SmallestSubstringContainingChars(test.Source,test.Counter);
if(result != test.ExpectedResult)
{
Console.WriteLine("Failed test: Source = {0}, result = {1}, expected = {2}", test.Source, result.ToString(), test.ExpectedResult.ToString());
return;
}
}
Console.WriteLine("All succeeded!");
}
static int SmallestSubstringContainingChars(string source, Dictionary<char, int> counter)
{
int start = 0;
while(start < source.Length && !counter.ContainsKey(source[start]))
++start;
if(start == source.Length)
return -1;
// If here, start is the index of the first character of source that is in the counter.
// Create a pointer end that will increment from start. Keep track of the minimum difference
// between the pointers whenever the pointers have spanned a substring that contains all the
// characters in the counter in their specified coun.
int? minspan = null;
for(int end = start; end < source.Length; ++end)
{
char c = source[end]; // character at end
if(counter.ContainsKey(c)) // ch is in counter
{
// Decrement count of character
counter[c] -= 1;
// If the count is less than 0, meaning we found a surplus of those
// characters in the current range, and if that character was the
// one at the start, we can move the start forward to the next character
// in the string and in the counter.
if(counter[c] < 0 && source[start] == c)
{
while(!counter.ContainsKey(source[++start]));
counter[c] += 1;
}
}
// If we've found all the characters in counter, then from start to end
// we have a substring that fits our criteria. Updated minspan.
if(counter.Values.All(count => count <= 0))
{
int span = end - start;
minspan = minspan == null ? span : Math.Min((int)minspan, span);
}
}
// If didn't find any range that spans all the characters in their specified count, return -1;
// else, return the length of the spanned substring.
return minspan == null ? -1 : ((int)minspan + 1);
}
public static void Main()
{
UnitTests();
}
}
[CODE]