UniLecs #Task. Split labels

Published in

UniLecs

2 min readSep 14, 2020

Задача: дана строка S, которая содержит только строчные английские буквы. Необходимо разделить эту строку на как можно больше частей, чтобы каждая буква появлялась не более чем в одной части. А сама функция должна возвращать список целых чисел, представляющих размер этих частей.

Входные данные: S — строка, содержащая только строчные английские буквы. Размер строки от 1 до 500.

Вывод: массив — элементы массива представляют размер частей разделенной строки S.

Пример:

S = “ababdeeda”
Output: [9] (Буква ‘a’ находится на 1м и последнем месте в строке, что не позволяет ее разбить более чем на 1 раздел)
S = “ababdeedhigtht”

Output: [4,4,6]

Пояснение: разбиение имеет следующий вид: “abab”, “deed”, “higtht”. Исходную строку максимально можно разделить только на 3 части, каждая буква исходной строки появляется не более чем в одной части.

Стоит заметить, что раздел исходной строки на след.части: “ababdeed”, “higtht” неверен. Здесь также каждая буква исходной строки появляется не более чем в одной части, однако это разбиение на меньшее кол-во частей.

Разбор

Попробуем разобрать на примере “ababdeedhigtht”.

Пусть мы ищем самый маленький раздел, тогда мы рассматриваем первую букву в строке, в нашем примере это буква ‘a’. Тогда согласно условию, только наш 1й раздел может содержать букву ‘a’. Значит нам надо найти последнее вхождение буквы ‘a’. Но между первым и последним вхождением буквы ‘a’ могут быть другие буквы, ктр могут также увеличить минимальный размер 1го раздела.

Для нашего примера 1й раздел будет “abab”.

То есть основная идея алгоритма: для каждой текущей буквы найти последнее ее вхождение в строку и увеличить размер текущего раздела. Если на iм шаге последнее вхождение текущего символа совпадает с номером шага i, значит мы обнаружили раздел, буквы которого находятся только в нем. Записываем размер этого раздела и обрабатываем аналогичным образом остальную часть строки.

Детали реализации смотрите ниже в коде.