Ctrl K

Общее начало после удаления

Сложная
Дан список слов words и число group. Для каждого индекса i мысленно уберите из списка слово words[i] и среди оставшихся выберите любые group слов (с разными индексами, сами слова могут совпадать) так, чтобы их общее начало — самый длинный префикс, общий для всех выбранных, — было как можно длиннее. Верните массив answer, где answer[i] — длина этого наибольшего общего префикса после удаления i-го слова. Если после удаления осталось меньше group слов, answer[i] = 0.
Пример 1
words=["cart", "care", "cat", "dog"], group=2 → [2, 2, 3, 3]

Без cart лучшая пара — care и cat с общим началом ca (2). Без care — cart и cat (2). Без cat или без dog остаются cart и care с началом car (3).

Пример 2
words=["sun", "sun", "moon"], group=3 → [0, 0, 0]

После любого удаления остаются два слова, а нужно три — везде 0.

Пример 3
words=["ab", "ab", "ab"], group=2 → [2, 2, 2]
Ограничения
  • 1 ≤ group ≤ len(words) ≤ 10⁵
  • 1 ≤ len(words[i]) ≤ 10⁴
  • Суммарная длина всех слов не больше 10⁵
  • Слова состоят из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиВсе способы расставить пробелы СложнаяСлова в буквенной сетке СложнаяСклеить в палиндром СложнаяЗеркальные блоки из слов СложнаяСлова из других слов Сложная
загружаем Python…
Вход
words=["cart", "care", "cat", "dog"], group=2
Ожидается
[2, 2, 3, 3]

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