📘

Partition Labels

Given a string s, partition it into as many parts as possible so that each letter appears in at most one part. Return the sizes of these parts.

Output sizes as space-separated integers.

Input:

ababcbacadefegdehijhklij

Output:

9 7 8

Reasoning:

The string s is scanned to find the last occurrence of each character, storing this information for later use.
The string is then iterated over, maintaining a window of characters that have not yet been partitioned, and expanding this window until it contains the last occurrence of every character within it.
When the end of the window is reached (i.e., the last occurrence of every character in the window), the size of the window is added to the output list, and the process repeats with the remaining unpartitioned characters.
This greedy approach ensures that each character appears in at most one partition, resulting in the maximum possible number of partitions, with sizes $9$ , $7$ , and $8$ for the given sample input.

Editor

Python 3.13.1

0/0

Run code to see test results.

📘