Partition String

Given a lowercase alphabet string s, partition s into as many pieces as possible such that each letter appears in at most one piece and return the sizes of the partitions as a list.

Constraints

• 0 ≤ n ≤ 100,000 where n is the length of s

https://binarysearch.com/problems/Partition-String

Examples

Example 1

Input

• s = cocoplaydae

Output

• answer = [4, 1, 1, 4, 1]

Explanation

The string is split to["coco", "p", "l", "ayda", "e"].

Solution