Partition Labels

Medium

You are given a string s.

You want to partition the string into as many parts as possible so that:

Each character appears in at most one part.
The parts must maintain their original order.
When all parts are concatenated, they must form the original string.

Return a list containing the size of each partition.

Example 1

Input

s = "ababcbacadefegdehijhklij"

Output

[9, 7, 8]

Explanation

The string can be partitioned as:

ababcbaca
defegde
hijhklij

Their lengths are:

9 7 8

Each character occurs in only one partition.

Example 2

Input

s = "eccbbbbdec"

Output

[10]

Explanation

The characters e, c, and b occur throughout the string, so the entire string must belong to one partition.

Constraints

1 <= s.length <= 500

s consists of lowercase English letters.

The string can be divided into one or more partitions.

Hints:

Hint 1

Find the last occurrence of every character in the string.

Hint 2

Start a partition from the current position and keep extending it until the current partition reaches the last occurrence of every character inside it.

Auto

Loading editor...

Input

Expected Output