← К задачам Режим собеседования 30:00
Обычный режим ← Предыдущая Следующая →

5214. Разбиение строки на независимые части

Medium 1 решил
Дана строка s из строчных латинских букв. Нужно разрезать её на куски слева направо так, чтобы выполнялось правило:

Если буква встретилась в каком‑то куске, то все её вхождения в строке должны лежать только в этом куске (одна и та же буква не может «перепрыгивать» через границу разреза).

Сделайте как можно больше таких кусков (режьте жадно, как только правило позволяет). Верните массив длин кусков по порядку слева направо.

Интуиция: буква «связывает» все позиции от своего первого до последнего вхождения — этот промежуток нельзя разорвать. Если связи пересекаются, куски сливаются.

Примеры:

Вход: ababcbacadefegdehijhklij
Выход: [9, 7, 8]
Объяснение: Смотрим, где каждая буква встречается в последний раз. Буквы a,b,c тянут первый кусок до позиции 8 → кусок длины 9: <code>ababcbaca | defegde | hijhklij</code>. Дальше аналогично получаются куски длин 7 и 8 → ответ <code>[9,7,8]</code>.
Вход: eccbbbbdec
Выход: [10]
Объяснение: Буквы <code>e</code> и <code>c</code> есть и в начале, и в конце строки. Их нельзя разнести по разным кускам, поэтому вся строка — один кусок длины 10 → <code>[10]</code>.
Вход: abc
Выход: [1, 1, 1]
Объяснение: Буквы a, b, c встречаются по одному разу и не пересекаются. Можно разрезать после каждой: <code>a | b | c</code> → <code>[1,1,1]</code>.

Ограничения:

1 <= s.length <= 500 s состоит из строчных английских букв

Теги:

Строки Жадные алгоритмы Хэш-таблица

Комментарии (0)

Зарегистрируйтесь или войдите, чтобы оставить комментарий

Пока нет комментариев. Будьте первым!