Задача с собеседования в Zopsmart
Задача с собеседования в Zopsmart
Даны строки s и t длиной m и n, соответственно. Верните
минимальную подстроку (подстроку окна)
строки s такую, что каждый символ из строки t (включая повторяющиеся) содержится в этом окне. Если такой подстроки не существует, верните пустую строку "".
Тестовые данные составлены таким образом, чтобы ответ был уникальным.
Follow up:
можете ли вы найти алгоритм, работающий за O(m + n) по времени?
Пример 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Объяснение: Подстрока минимального окна "BANC" включает символы 'A', 'B' и 'C' из строки t.
Пример 2:
Input: s = "a", t = "a"
Output: "a"
Объяснение: Вся строка s является минимальным окном.
Пример 3:
Input: s = "a", t = "aa"
Output: ""
Объяснение: Обе 'a' из строки t должны быть включены в окно. Поскольку самое большое окно s имеет только одну 'a', возвращаем пустую строку.
Ограничения:
m == s.length
n == t.length
1 <= m, n <= 10⁵
s и t состоят из английских букв верхнего и нижнего регистра.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Используем
алгоритм
"скользящего окна"
с двумя указателями и хэш-таблицу
.
Расширяем окно правым указателем, пока не набираем все необходимые символы. Когда окно становится валидным, пробуем сжать его левым указателем, избавляясь от лишних символов, пока окно не перестанет удовлетворять условиям.
Создаём два словаря:
freqT - хранит частоту символов строки t, не изменяется;
freqWindow - хранит частоту символов текущего окна, изменяется при движении указателей.
Заполняем словарь freqT:
- С помощью метода get(ch, 0) возвращаем текущую частоту символа, либо 0, если символ ещё не встречался. Увеличиваем счётчик символа на 1.
Переменные:
need - кол-во
уникальных
символов в t, которые
нужно набрать
;
have - кол-во
уникальных
символов, которые
уже есть
в текущем окне.
res - индексы минимального найденного окна;
resLen - длина минимального окна (float("inf"), чтобы записать первое валидное окно в кач-ве минимального).
Расширяем окно
, проходя по строке s указателем r:
- Добавляем каждый новый символ в словарь freqWindow и увеличиваем его частоту на 1;
- Если текущий символ находится в freqT и после добавления его частота в freqWindow равна требуемой в freqT: увеличиваем have.
Сжимаем
окно
, пока текущее окно содержит все необходимые символы:
- Сравниваем длину окна с длиной найденного ранее (resLen). Если текущее окно короче: сохраняем его индексы в res и обновляем resLen;
- Так как будем сдвигать левый указатель: текущий символ под его индексом покинет окно - уменьшаем счётчик этого символа в freqWindow на 1;
- Проверяем, осталось ли окно валидным:
если s[l] есть в freqT и кол-во символа в freqWindow меньше, чем необходимо (freqT), значит, мы потеряли один из требуемых уникальных символов - уменьшаем have на 1;
- Сдвигаем левый указатель вправо.
Если have становится меньше need, цикл завершается, мы возвращаемся к расширению окна правым указателем.
Возвращаем срез по сохранённым индексам минимального найденного окна.
Сложность
O(m + n) - по времени (l и r двигаются только вправо и ограничены длиной s - O(m), заполнение freqT по строке t - O(n))
O(1) - по памяти (фиксированное кол-во букв алфавита)
Код
class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(s) < len(t):
return ""
freqT, freqWindow = {}, {}
for ch in t:
freqT[ch] = 1 + freqT.get(ch, 0)
need, have = len(freqT), 0
res, resLen = [-1, -1], float("inf")
l = 0
for r in range(len(s)):
ch = s[r]
freqWindow[ch] = 1 + freqWindow.get(ch, 0)
if ch in freqT and freqWindow[ch] == freqT[ch]:
have += 1
while have == need:
if (r - l + 1) < resLen:
res = [l, r]
resLen = (r - l + 1)
freqWindow[s[l]] -= 1
if s[l] in freqT and freqWindow[s[l]] < freqT[s[l]]:
have -= 1
l += 1
l, r = res
return s[l:r+1] if resLen != float("inf") else ""
@algoses
Откликнуться в Telegram →
⚠️ Никогда не платите «за оформление» или «гарантию трудоустройства» — это признак мошенников. Работа ТРУ не несёт ответственности за содержание вакансии.
