Ctrl K

Почти совпадающая выборка

Средняя
Даны строки text и pattern, причём pattern короче. Выберите из text ровно len(pattern) позиций в порядке возрастания и выпишите стоящие на них буквы. Выборка подходит, если полученная строка совпадает с pattern либо отличается от неё ровно в одной букве (одну букву разрешается заменить). Верните подходящую выборку — список позиций, — который наименьший в словарном порядке как список чисел (сравнивается первая позиция, при равенстве вторая и т. д.). Если подходящих выборок нет, верните пустой список. Важно: минимизируется сам список позиций, а не строка из выбранных букв.
Пример 1
text="xcaty", pattern="bat" → [0, 2, 3]

Берём позиции 0, 2, 3: буквы "xat". Заменив x на b, получаем "bat". Набор [1, 2, 3] тоже подходит, но [0, 2, 3] меньше.

Пример 2
text="cabd", pattern="abd" → [0, 2, 3]

Точное совпадение — позиции [1, 2, 3]. Но можно взять позицию 0 и заменить c на a, а "bd" найти на позициях 2 и 3: [0, 2, 3] меньше.

Пример 3
text="aaaa", pattern="bcd" → []

Совпасть должны хотя бы две буквы из трёх, а в text нет ни b, ни c, ни d — ответ пустой.

Ограничения
  • 1 ≤ len(pattern) < len(text) ≤ 3·10⁵
  • Обе строки состоят из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиЗеркальная нарезка строки СложнаяНепересекающиеся длинные палиндромы СложнаяСамый длинный зеркальный кусок СредняяСколько кусков-палиндромов в строке СредняяСкобки со звёздочками Средняя
загружаем Python…
Вход
text="xcaty", pattern="bat"
Ожидается
[0, 2, 3]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 154 теста на сервере, включая скрытые.