Partition Labels
MediumGreedy
You are given a string s. Split it into as many contiguous pieces as possible so that every letter appears in at most one piece. In other words, all copies of any given letter must end up in the same piece.
The pieces, joined back together in order, must give s. Return a list of the lengths of the pieces, in order from left to right.
Example 1
- Input:
- s = "abacdcfeghfg"
- Output:
- [3, 3, 6]
- Explanation
alast appears at index 2, so the first piece isaba. Thencreaches index 5, givingcdc. Finallyfandgoverlap all the way to the end, so the rest,feghfg, is one piece.
Example 2
- Input:
- s = "xyzzyxq"
- Output:
- [6, 1]
- Explanation
xappears at indices 0 and 5, which forcesxyzzyxinto one piece.qappears only once at the end and stands alone.
Example 3
- Input:
- s = "abc"
- Output:
- [1, 1, 1]
- Explanation
- No letter repeats, so every letter can be its own piece.
Constraints
- 1 ≤
s.length≤ 500 scontains only lowercase English letters