Minimum Window Substring

Сложная№76переменный размер

Даны две строки, s и t. Найди самый короткий кусок s из подряд идущих букв, в котором есть все буквы t, причём столько раз, сколько их в t. Если такого нет, ответ — пустая строка. Наш пример: s = «baxcab», t = «abc» — ответ «cab».

76 Minimum Window SubstringРазбор · 1×

Пример: s = «baxcab», t = «abc». Под s — need: сколько каких букв окну ещё не хватает. 0 — бледный, меньше 0 — запасная буква.

0b1a2x3c4a5bneeda1b1c1missing–best–
ещё не дошли, не хватаетокновходящая буквауходящая буква, запаснаявышло из окна, счётчик 0покрывает t

Считаем буквы t: окно должно собрать {a: 1, b: 1, c: 1}

01/57
сначала · назад · пуск · шаг
Скорость
1function minWindow(s, t):
2 need = count of each letter in t // missing keys: 0
3 missing = len(t)
4 left = 0
5 best = ""
6 for right from 0 to len(s) - 1:
7 if need[s[right]] > 0:
8 missing = missing - 1
9 need[s[right]] = need[s[right]] - 1
10 while missing == 0:
11 if best == "" or right - left + 1 < len(best):
12 best = s[left .. right]
13 need[s[left]] = need[s[left]] + 1
14 if need[s[left]] > 0:
15 missing = missing + 1
16 left = left + 1
17 return best
состояние
need
{a: 1, b: 1, c: 1}
missing
–
left
–
right
–
best
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. missing — сколько букв t окну ещё не хватает. Оно меняется, только когда счётчик переходит через 0, поэтому вопрос «покрывает ли окно t?» решается за O(1), без сравнения счётчиков.
  2. Буква со счётчиком меньше 0 — запасная: если её убрать, missing останется 0. Поэтому окно сужается мимо запасных и ненужных t букв и останавливается, только когда теряет обязательную.
  3. Для каждого right окно сужается, пока оно ещё покрывает t, поэтому измеряется самое короткое покрывающее окно, которое кончается на right, а best хранит самое короткое из них.

Сложность

Время O(n + m), где n и m — длины s и t: t считается один раз, а каждая буква s один раз входит в окно и не больше одного раза выходит. Память O(k) на счётчики k разных букв.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.