0230MediumHash TableTwo PointersStringGreedy

Duty Roster Blocks

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def duty_roster_blocks(roster: str) -> list[int]:

Java

public List<Integer> dutyRosterBlocks(String roster)

The intended approach

Time O(n)Space O(n) for the returned block counts; the last-slot record holds at most 26 codes

Record the last slot each code is worked in. Then sweep the roster carrying the furthest of those last slots among the codes met since the current block opened, widening it whenever a code reaches further ahead. When the sweep position lands on that furthest slot, no code inside the block appears later on, so the block is closed and its slot count recorded.

Pythonentry point: duty_roster_blocks

def duty_roster_blocks(roster):
    last_slot = {}
    for i, code in enumerate(roster):
        last_slot[code] = i
    blocks = []
    start = 0
    reach = 0
    for i, code in enumerate(roster):
        if last_slot[code] > reach:
            reach = last_slot[code]
        if i == reach:
            blocks.append(i - start + 1)
            start = i + 1
    return blocks

The obvious version

For every position, compare the set of codes in the block so far against the set of codes in the whole remainder of the roster and close the block as soon as those two sets are disjoint. O(n^2).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_duty_roster_blocks(roster):
    n = len(roster)
    blocks = []
    start = 0
    for cut in range(1, n + 1):
        head = set(roster[start:cut])
        tail = set(roster[cut:])
        if not (head & tail):
            blocks.append(cut - start)
            start = cut
    return blocks

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in