Greedy The best choice now

494. Partition Labels

You are given a string s of lowercase letters. Cut it into as many parts as you can, so that each letter appears in at most one part. Every copy of a letter must then sit in the same part.

A part is a run of characters next to each other, and the parts, read in order, make up s again. Return the size of each part, from left to right.

Example 1

Input: s = "abacdcdeffe"

Output: [3,4,4]

Explanation: The parts are aba, cdcd and effe. Each letter stays inside one part. Cutting cdcd after cdc would leave one d on each side.

Example 2

Input: s = "abcab"

Output: [5]

Explanation: The two as must share a part, and so must the two bs. Together they cover the whole string, so no cut is possible.

Example 3

Input: s = "xyz"

Output: [1,1,1]

Explanation: No letter repeats, so every letter is a part on its own.

Check your understanding

Work out the answer for this input before you write any code.

s = "abacbd"

Constraints

1 ≤ s.length ≤ 10⁵
s holds only the lowercase letters a to z.

Clarifying questions

What you would ask an interviewer before writing any code.