Substract shortest string containing all search criteria
<p>I have a problem to solve where given a string <code>source</code> and a collection of search criteria <code>criteria</code>, the algorithm has to return the shortest possible substring of <code>source</code> that contains all items of <code>criteria</code>.</p>

<p>=================================</p>

<p><strong>UPDATE</strong></p>

<ul>
<li>The same search criteria might be in the source string multiple
times. In that case, it is required to return the sub-string
containing the particular instance of the search criteria such that
it is the shortest among all possible sub-strings.</li>
<li>The search items can contain spaces in them such as <code>hello world</code></li>
<li>The order in which the search criteria are found does not matter as long as they are all in the resultant sub-string</li>
</ul>

<p>==================================</p>

<pre><code>String source = "aaa wwwww fgffsd ththththt sss sgsgsgsghs bfbfb hhh sdfg kkk dhdhtrherhrhrthrthrt ddfhdetehehe kkk wdwd aaa vcvc hhh zxzx sss nbnbn";
List&lt;String&gt; criteria = new List&lt;string&gt; { "kkk", "aaa", "sss", "hhh" };
</code></pre>

<p>The input above should return the following substring: <code>kkk wdwd aaa vcvc hhh zxzx sss</code></p>

<p>Unfortunately, I spent a lot of time trying to write such an algorithm but I couldn't get it just right. Below is the code I have got so far:</p>

<pre><code>public struct Extraction
{
    public int Start { get; set; }
    public int End { get; set; }
    public int Length
    {
        get
        {
            var length = this.End - this.Start;
            return length;
        }
    }

    public Extraction(int start, int end)
    {
        this.Start = start;
        this.End = end;
    }
}

public class TextExtractor
{
    private String _source;
    private Dictionary&lt;String, List&lt;Int32&gt;&gt; _criteriaIndexes;
    private Dictionary&lt;String, int&gt; _entryIndex;

    public TextExtractor(String source, List&lt;String&gt; searchCriteria)
    {
        this._source = source;
        this._criteriaIndexes = this.ExtractIndexes(source, searchCriteria);
        this._entryIndex = _criteriaIndexes.ToDictionary(x =&gt; x.Key, v =&gt; 0);
    }

    public String Extract()
    {
        List&lt;Extraction&gt; possibleExtractions = new List&lt;Extraction&gt;();

        int index = 0;
        int min = int.MaxValue;
        int max = 0;
        bool shouldStop = false;
        while (index &lt; _criteriaIndexes.Count &amp;&amp; !shouldStop)
        {
            Boolean compareWithAll = index == _criteriaIndexes.Count - 1;
            if (!compareWithAll)
            {
                var current = _criteriaIndexes.ElementAt(index);
                this.CalculateMinMax(current, ref min, ref max);
                index++;
            }
            else
            {
                var entry = _criteriaIndexes.Last();
                while (_entryIndex[entry.Key] &lt; entry.Value.Count)
                {
                    int a = min;
                    int b = max;
                    this.CalculateMinMax(entry, ref a, ref b);

                    _entryIndex[entry.Key]++;
                    Extraction ext = new Extraction(a, b);
                    possibleExtractions.Add(ext);
                }
                int k = index - 1;

                while (k &gt;= 0)
                {
                    var prev = _criteriaIndexes.ElementAt(k);
                    if (prev.Value.Count - 1 &gt; _entryIndex[prev.Key])
                    {
                        _entryIndex[prev.Key]++;
                        break;
                    }
                    else
                    {
                        k--;
                    }
                }
                shouldStop = _criteriaIndexes.All(x =&gt; x.Value.Count - 1 &lt;= _entryIndex[x.Key]);
                _entryIndex[entry.Key] = 0;
                index = 0;
                min = int.MaxValue;
                max = 0;
            }
        }

        Extraction shortest = possibleExtractions.First(x =&gt; x.Length.Equals(possibleExtractions.Min(p =&gt; p.Length)));
        String result = _source.Substring(shortest.Start, shortest.Length);
        return result;
    }

    private Dictionary&lt;String, List&lt;Int32&gt;&gt; ExtractIndexes(String source, List&lt;String&gt; searchCriteria)
    {
        Dictionary&lt;String, List&lt;Int32&gt;&gt; result = new Dictionary&lt;string, List&lt;int&gt;&gt;();
        foreach (var criteria in searchCriteria)
        {
            Int32 i = 0;
            Int32 startingIndex = 0;
            var indexes = new List&lt;int&gt;();
            while (i &gt; -1)
            {
                i = source.IndexOf(criteria, startingIndex);
                if (i &gt; -1)
                {
                    startingIndex = i + 1;
                    indexes.Add(i);
                }
            }
            if (indexes.Any())
            {
                result.Add(criteria, indexes);
            }

        }
        return result;
    }

    private void CalculateMinMax(KeyValuePair&lt;String, List&lt;int&gt;&gt; current, ref int min, ref int max)
    {
        int j = current.Value[_entryIndex[current.Key]];
        if (j &lt; min)
        {
            min = j;
        }
        int indexPlusWordLength = j + current.Key.Length;
        if (indexPlusWordLength &gt; max)
        {
            max = indexPlusWordLength;
        }
    }
}
</code></pre>

<p>I would appreciate it if someone could point out where did I go wrong in my algorithm. Moreover, I kinda feel this is a very naive implementation. Maybe there is a better approach to solve this problem than trying to try out combinations of indexes?</p>

<p>Thanks!</p>