Вам дана строка s. Мы хотим разделить строку на как можно больше частей, чтобы каждая буква встречалась не более чем в одной части.

Обратите внимание, что разбиение сделано таким образом, что после объединения всех частей по порядку результирующая строка должна быть s.

Возвращает список целых чисел, представляющих размер этих частей.


class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        count = {}
        res = []
        i, length = 0, len(S)

        for j in range(length):
            c = S[j]
            count[c] = j

        curLen = 0
        goal = 0

        while i < length:
            c = S[i]
            goal = max(goal, count[c])
            curLen += 1

            if goal == i:
                res.append(curLen)
                curLen = 0
            i += 1

        return res

Войти в полноэкранный режим

Выйти из полноэкранного режима