Как найти наименьшую подстроку, которая содержит все символы от данной строки?

Решение JavaScript способом "в лоб":

function shortestSubStringOfUniqueChars(s){
	var uniqueArr = [];
	for(let i=0; i<s.length; i++){
		if(uniqueArr.indexOf(s.charAt(i)) <0){
			uniqueArr.push(s.charAt(i));
		}
	}

	let windoww = uniqueArr.length;

	while(windoww < s.length){
		for(let i=0; i<s.length - windoww; i++){
			let match = true;
			let tempArr = [];
			for(let j=0; j<uniqueArr.length; j++){
				if(uniqueArr.indexOf(s.charAt(i+j))<0){
					match = false;
					break;
				}
			}
		let checkStr
		if(match){
			checkStr =  s.substr(i, windoww);
			for(let j=0; j<uniqueArr.length; j++){
				if(uniqueArr.indexOf(checkStr.charAt(j))<0){
					match = false;
					break;
				}
			}
		}
		if(match){
		    return checkStr;
		}
 	 }
 	 windoww = windoww + 1;
	}
}

console.log(shortestSubStringOfUniqueChars("ABA"));

Вот O(n) решение. Основная идея проста: для каждого начального индекса найти наименьший конечный индекс, такой, чтобы подстрока содержала все необходимые буквы. Хитрость в том, что наименьший конечный индекс увеличивается по ходу выполнения функции, поэтому с небольшой поддержкой структуры данных мы рассматриваем каждый символ не более двух раз.

В Python:

from collections import defaultdict

def smallest(s1, s2):
    assert s2 != ''
    d = defaultdict(int)
    nneg = [0]  # number of negative entries in d
    def incr(c):
        d[c] += 1
        if d[c] == 0:
            nneg[0] -= 1
    def decr(c):
        if d[c] == 0:
            nneg[0] += 1
        d[c] -= 1
    for c in s2:
        decr(c)
    minlen = len(s1) + 1
    j = 0
    for i in xrange(len(s1)):
        while nneg[0] > 0:
            if j >= len(s1):
                return minlen
            incr(s1[j])
            j += 1
        minlen = min(minlen, j - i)
        decr(s1[i])
    return minlen

Edit: по-видимому, существует алгоритм O(n) (см. ответ алгоритмиста). Очевидно, что это превзойдет [наивную] базовую линию, описанную ниже!

Жаль, что я должен пойти... Я немного подозреваю, что мы можем получить O(n). Я заеду завтра, чтобы увидеть победителя ;-) Веселитесь!

Предварительный алгоритм:
Общая идея состоит в том, чтобы последовательно попытаться использовать символ из str2, найденный в str1, в качестве начала поиска (в любом / обоих направлениях) всех других букв str2. Сохраняя значение «длина наилучшего соответствия до сих пор», мы можем прерывать поиск, когда они превышают это. Другие эвристики, вероятно, могут быть использованы для дальнейшего прерывания неоптимальных (пока) решений. Выбор порядка начальных букв в str1 имеет большое значение; предлагается начинать с буквы (букв) str1, которые имеют наименьшее количество, и пытаться с другими буквами, увеличивающимися, в последующих попытках.

  [loose pseudo-code]
  - get count for each letter/character in str1  (number of As, Bs etc.)
  - get count for each letter in str2
  - minLen = length(str1) + 1  (the +1 indicates you're not sure all chars of 
                                str2 are in str1)
  - Starting with the letter from string2 which is found the least in string1,
    look for other letters of Str2, in either direction of str1, until you've 
    found them all (or not, at which case response = impossible => done!). 
    set x = length(corresponding substring of str1).
 - if (x < minLen), 
         set minlen = x, 
         also memorize the start/len of the str1 substring.
 - continue trying with other letters of str1 (going the up the frequency
   list in str1), but abort search as soon as length(substring of strl) 
   reaches or exceed minLen.  
   We can find a few other heuristics that would allow aborting a 
   particular search, based on [pre-calculated ?] distance between a given
   letter in str1 and some (all?) of the letters in str2.
 - the overall search terminates when minLen = length(str2) or when 
   we've used all letters of str1 (which match one letter of str2)
   as a starting point for the search