Partition Labels

Medium~25 min

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

Examples

Example 1

Input: s = "ababcbacadefegdehijhklij"

Output: [9,7,8]

Explanation: The partition is "ababcbaca", "defegde", "hijhklij". Each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect because it has fewer parts.

Example 2

Input: s = "eccbbbbdec"

Output: [10]

Explanation: All characters overlap, so the entire string is one partition.

Constraints

1 <= s.length <= 500
s consists of lowercase English letters
Expected time complexity: O(n)

Code

Ctrl+EnterRun|Ctrl+⇧+EnterSubmit

Output

Run your code to see results

Use Cmd+Enter to run