Partition Labels

Cut s into as many parts as possible so that each letter appears in at most one part. Return the sizes of the parts, in order.

For "ababcbacadefegdehijhklij" the answer is [9, 7, 8].

The starter code compares the letters on both sides of every cut position. It is correct but too slow for long strings.

Examples

Example 1

Input:

partition_labels('ababcbacadefegdehijhklij')

Output:

[9, 7, 8]

Example 2

Input:

partition_labels('eccbbbbdec')

Output:

[10]

Constraints

• 0 <= len(s) <= 200000
• Lower-case letters.