You are given a string s. Your task is to divide the string into as many parts as possible such that each letter appears in at most one part.

In other words, no character should occur in more than one partition. After concatenating all parts in order, the result should be the original string s.

For example, given s = "bcbcdd", a valid partition is ["bcbc", "dd"]. However, partitions like ["bcb", "cdd"] or ["bc", "bc", "dd"] are invalid because some letters appear in multiple parts.

Return a list of integers representing the sizes of these partitions.

Constraints:

• $1\leq$ s.length $\leq500$

• s consists of lowercase English letters.

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding on how to solve this problem.

Implement your solution in the following coding playground.