Partition Labels
Real-world version: Duty Roster BlocksThe statement here is our own: the same inputs, outputs and technique.
A workshop posts its watch roster as roster, a string of lowercase letters. The letter in each slot is the code of the technician standing that watch, and the slots run left to right in the order they will be worked.
The supervisor wants to hand the roster out in consecutive blocks. Every slot belongs to exactly one block and the blocks stay in order, so reading the blocks one after another spells roster again. A block may only be handed out if no technician's code turns up in any other block. Split the roster into as many blocks as that allows, which fixes one answer.
Return the number of slots in each block, in the order the blocks are worked.
Examples
Example 1
- Input
- roster = "zzxyxwwv"
- Output
- [2, 3, 2, 1]
The blocks are `zz`, `xyx`, `ww` and `v`, so their slot counts are 2, 3, 2 and 1. Codes z, x, y, w and v each sit inside one block only.
Example 2
- Input
- roster = "aabbaacc"
- Output
- [6, 2]
The blocks are `aabbaa` and `cc`. Codes a and b are confined to the first block and code c to the second.
Example 3
- Input
- roster = "wxyz"
- Output
- [1, 1, 1, 1]
No code repeats anywhere in the roster, and the four one-slot blocks each hold a different code.
Constraints
- 1 <= roster.length <= 500
- roster holds lowercase English letters only
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def duty_roster_blocks(roster: str) -> list[int]:public List<Integer> dutyRosterBlocks(String roster)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's