Наименьшая подстрока, состоящая из максимально различных символов строки

Question

Учитывая строку, мне нужно найти наименьшую подстроку, которая содержит все уникальные символы в строке. Вот три примера:

Input: "AABBBCBB"    Shortest substring: "ABBBC"    
Input: "AABBBCBBAC", Shortest substring: "BAC"        
Input: "aabcaadcc",  Shortest substring: "bcaad"

Уникальными символами в первой подстроке являются 'A', 'B' и 'C'. Подстроки, содержащие эти символы: 'AABBBC', 'AABBBCB', 'AABBBCBB', 'ABBBC', 'ABBBCB' и 'ABBBCBB'. Самый короткий из них - 'ABBBC'. Если есть две или более короткие подстроки, может быть возвращена любая из них.

Answer 1

Код

def doit(str)
  uniq_chars = str.each_char.uniq
  nbr_uniq_chars = uniq_chars.size
  last_idx = str.size - 1
  shortest = { idx: 0, size: str.size }
  last_start_idx = last_idx - nbr_uniq_chars + 1
  (0..last_start_idx).each do |start_idx|
    first_end_idx = start_idx + nbr_uniq_chars - 1
    last_end_idx = start_idx + shortest[:size] - 1
    (first_end_idx..last_end_idx).each do |end_idx|
      if (uniq_chars - str[start_idx..end_idx].chars).empty?
        shortest = { idx: start_idx,
                     size: end_idx - start_idx + 1 }
        break
      end
    end
  end
  str[shortest[:idx], shortest[:size]]
end

Примеры

doit "AABBBCBB"   #=> "ABBBC" 
doit "AABBBCBBAC" #=> "BAC" 
doit "aabcaadcc"  #=> "bcaad"

Пояснение

Предположим:

str = "AABBBCBB"

Шаги следующие.

uniq_chars = str.each_char.uniq
  #=> ["A", "B", "C"] 
nbr_uniq_chars = uniq_chars.size
  #=> 3 
last_idx = str.size - 1
  #=> 7 
shortest = { idx: 0, size: str.size }
  #=> {:idx=>0, :size=>8} 

shortest описывает самую короткую найденную на данный момент подстроку. Это подстрока

str[shortest[:idx], shortest[:size]]

Изначально она описывает всю строку. Продолжая,

last_start_idx = last_idx - nbr_uniq_chars + 1
  #=> 5

Я буду фиксировать начальный индекс, start_idx, первоначально в нуле, а затем рассмотрим все подстроки, начинающиеся с этого индекса. Нет никаких оснований считать start_idx > last_idx как в этом случае str[start_idx..-1].size < nbr_uniq_chars, и, следовательно, это невозможно.

enum1 = (0..last_start_idx).each
  #=> #<Enumerator: 0..5:each> 
start_idx = enum1.next
  #=> 0 
first_end_idx = start_idx + nbr_uniq_chars - 1
  #=> 3 
last_end_idx = start_idx + shortest[:size] - 1
  #=> 7

enum2 = (first_end_idx..last_end_idx).each
  #=> #<Enumerator: 3..4:each> 
end_idx = enum2.next
  #=> 2 
a = str[start_idx..end_idx].chars
  #=> str[0..2].chars
  #=> ["A", "A", "B"] 
b = uniq_chars - a
  #=> ["A", "B", "C"] - ["A", "A", "B"] 
  #=> ["C"]
b.empty?
  #=> false, so do not update `shortest`

end_idx = enum2.next
  #=> 3 
a = str[start_idx..end_idx].chars
  #=> ["A", "A", "B", "B"] 
b = uniq_chars - a
  #=> ["C"] 
b.empty?
  #=> false, so do not update `shortest`

end_idx = enum2.next
  #=> 4 
a = str[start_idx..end_idx].chars
  #=> ["A", "A", "B", "B", "B"] 
b = uniq_chars - a
  #=> ["C"] 
b.empty?
  #=> false, so do not update `shortest`

end_idx = enum2.next
  #=> 5 
a = str[start_idx..end_idx].chars
  #=> ["A", "A", "B", "B", "B", "C"] 
b = uniq_chars - a
  #=> [] 
b.empty?
  #=> true

Мы нашли подстроку, которая содержит все уникальные символы в строке, но более того, мы знаем, что она короче предыдущей самой короткой подстроки. (Не нужно проверять!) Поэтому мы обновляем shortest:

shortest = { idx: start_idx, size: end_idx - start_idx + 1 }
  #=> {:idx=>0, :size=>6}

, который описывает подстроку:

str[shortest[:idx], shortest[:size]]
  #=> "AABBBC"

Нам больше не нужно выполнять end_idx = enum2.next для этого значения из start_idx, потому что мы знаем, что связанная подстрока будет начинаться с только что идентифицированной строки и, следовательно, будет иметь все уникальные символы в str, но будет длиннее, чем только что найденная подстрока. Поэтому мы выполняем:

break

, завершая внутренний l oop. Следующим шагом будет создание второго элемента из enum1 и go оттуда:

start_idx = enum1.next
  #=> 1 
first_end_idx = start_idx + nbr_uniq_chars - 1
  #=> 3 
last_end_idx = start_idx + shortest[:size] - 1
  #=> 6

В результате shortest будет обновлено (в последний раз) до:

shortest
  #=> { idx: 1, size: 5 }

Остальные расчеты аналогичны.

Answer 2

Я решил этот алгоритм с помощью следующего подхода.

def max_distinct_char(str)
  str.chars.uniq.count
end

def smallest_subset_str(str)
  str_length = str.length
  max_distinct = max_distinct_char(str)

  min_str_len = str_length

  for j in (0..str_length)
    for k in (0..str_length)
      sub_str = str[j..k]
      sub_str_length = sub_str.length
      sub_distinct_char_length = max_distinct_char(sub_str)

      if (sub_str_length < min_str_len && max_distinct == sub_distinct_char_length)
        min_str_len = sub_str_length
        sub_string = sub_str
      end
    end
  end
  sub_string
end

Используя вышеприведенные методы, мы можем получить результаты как

smallest_subset_str "AABBBCBB"   #=> "ABBBC" 
smallest_subset_str "AABBBCBBAC" #=> "BAC" 
smallest_subset_str "aabcaadcc"  #=> "bcaad"