Задача с собеседования в Яндекс
Дан некоторый алфавит и строка. Необходимо найти в строке панграмму минимальной длины, где панграмма - это такая подстрока исходной строки, в которую входят все буквы из алфавита (но необязательно только они).
Пример:
A = {a, b, c}
s = "dfagabkaceb"
Ответом могут быть строки "bkac" и "aceb"
Решение:
Халявные два указателя буквально подарят тебе оффер
Будем двигать правый указатель, расширяя подстроку, пока не включим все символы из алфавита. Как только все символы оказались в окне, будем двигать левый указатель, обновляя ответ и сохраняя все необходимые символы.
Обязательно надо проверить, что панграмма с концом в конце исходной строки также рассматривается.
Асимптотика O(N)
В целом, можно предложить алгоритм без сдвига начала строки за O(NS), что тоже прокатит
Типичные ошибки:
1) Не обработать ненахождение панграммы в принципе
2) Неправильно похендлить алфавит длиной один
3) Ненахождение ответа в конце текста
@algoses
Post #305
6.96K
- 👍 17
- ❤ 4
- 👏 1
- 💊 1