Partition Labels

Split a string into as many parts as possible so each character appears in only one part.

greedy string hashmap

You are given a string `s` consisting of lowercase English letters. Your task is to partition the string into as many parts as possible such that each letter appears in at most one part. A partition is a set of contiguous substrings that concatenate to form `s`. Return a list of integers representing the size of each part.

Implement the function `partition_labels(s: str) -> list[int]`.

**Input:** A string `s` with length between 1 and 500, consisting of lowercase letters.

**Output:** A list of integers, each being the length of a part, in the order they appear in the original string.

Constraints

1 <= len(s) <= 500
`s` contains only lowercase English letters.
The solution should run in O(n) time, where n is the length of the string.

Example

>>> partition_labels("ababcbacadefegdehijhklij")
[9, 7, 8]

>>> partition_labels("eccbbbbdec")
[10]

>>> partition_labels("abc")
[1, 1, 1]

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

First, record the last occurrence index of each character.

Scan the string and extend a current partition's end to the last occurrence of each character seen so far.

When the current index reaches the partition's end, cut the partition and start a new one.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.