Найдите минимальную ширину окна в строке x
, которая содержит все символы другой строки y
. Например:
String x = "coobdafceeaxab"
String y = "abc"
Ответ должен быть 5, потому что самая короткая подстрока в x
, которая содержит все три буквы из y
, - это "bdafc".
Я могу представить себе наивное решение со сложностью O(n^2 * log(m))
, где n = len(x)
и m = len(y)
. Может ли кто-нибудь предложить лучшее решение? Спасибо.
Обновить: теперь подумайте об этом, если я изменю свой набор на tr1::unordered_map
, тогда я могу сократить сложность до O(n^2)
, потому что вставка и удаление должны быть O(1)
.