mediumGreedyPure DSA~25 min
Partition String Into Maximum Label-Disjoint Parts
Split a string into the most pieces possible so that no letter appears in more than one piece — a partitioning used to chunk logs by non-overlapping tag scopes.
Problem
Given a string s, partition it into as many contiguous parts as possible so that each letter appears in at most one part. Return a list of the sizes of these parts, in order.
Input
A string s of lowercase English letters.
Output
A list of integers: the length of each partition in order.
Constraints
- 1 <= s.length <= 500
- s consists of lowercase English letters.
Examples
Example 1
Input
s = "ababcbacadefegdehijhklij"
Output
[9,7,8]
The first part ends where the last a/b/c resolve; then d/e/f/g; then the rest.
Example 2
Input
s = "eccbbbbdec"
Output
[10]
All letters' spans overlap, forcing a single part.