4124. Окна из k различных слов
Medium
1 решил
Дан список слов
Смотрите на каждое окно из ровно k подряд идущих слов: окно, начинающееся с индекса
Нужно найти все стартовые индексы
Верните список таких индексов по возрастанию.
Если
Пример при
• i=0: bar, foo — разные → подходит;
• i=1: foo, bar — разные → подходит;
• i=2: bar, the — разные → подходит;
ответ
words и целое число k ≥ 1.Смотрите на каждое окно из ровно k подряд идущих слов: окно, начинающееся с индекса
i, — это words[i], words[i+1], …, words[i+k−1].Нужно найти все стартовые индексы
i, для которых в этом окне все k слов различны (никакое слово не повторяется внутри окна).Верните список таких индексов по возрастанию.
Если
k больше длины списка или список пуст — верните []. При k = 1 каждое одиночное слово считается окном без повторов → индексы 0 … n−1.Пример при
k = 2 и words = ["bar", "foo", "bar", "the"]:• i=0: bar, foo — разные → подходит;
• i=1: foo, bar — разные → подходит;
• i=2: bar, the — разные → подходит;
ответ
[0, 1, 2].Примеры:
Вход:
{"words": ["bar", "foo", "bar", "the"], "k": 2}
Выход:
[0, 1, 2]
Объяснение: Окна длины 2: (bar,foo), (foo,bar), (bar,the) — во всех слова разные → [0, 1, 2].
Вход:
{"words": ["a", "b", "c", "a"], "k": 3}
Выход:
[0, 1]
Объяснение: Окно с i=0: a,b,c — все разные. Окно с i=1: b,c,a — все разные. Окно с i=2 уже не умещается (нужно 3 слова). → [0, 1].
Вход:
{"words": ["a", "a", "a"], "k": 2}
Выход:
[]
Объяснение: Любое окно из двух слов — (a,a), внутри повтор → [].
Вход:
{"words": ["x"], "k": 1}
Выход:
[0]
Объяснение: k=1: одно слово без пары для повтора → [0].
Ограничения:
0 <= words.length <= 10^5
1 <= k
суммарная длина всех слов <= 10^6
слова состоят из букв и цифр
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!