Gym Sets With Rest
Your coach hands you a workout card listing sets to do, each tagged with the muscle group it works: L for legs, C for chest, B for back, and so on. You do one thing per slot of time: either one set, or rest. You may do the sets in any order you like.
The coach has one rule: after a set for some muscle group, at least rest other slots must pass before you work that same group again. Those slots can be sets for other groups or plain rest. You want to finish the card in as few slots as possible.
Your task
Write fewestSlots(sets, rest). sets is a string of uppercase letters, one per set; equal letters are the same muscle group. Between two sets of the same group there must be at least rest other slots. Return the smallest total number of slots, counting rest slots, needed to do every set.
An empty card takes 0 slots. With rest = 0 there is no restriction.
fewestSlots(sets: string, rest: int) → int
Examples
sets = "LLLC" rest = 2
7
One best order is L C _ L _ _ L, where _ is a rest slot. Every pair of L sets has 2 slots between them. The three L sets alone force this length: the first and last L are at least 2 × 3 = 6 slots apart, so at least 7 slots in total. The one C set fills a gap but cannot shorten it.
sets = "LLCCAB" rest = 1
6
L C L C A B works with no rest at all: each L and each C has another group's set right after it. You can never beat 6, since there are 6 sets.
Constraints
- 0 ≤ sets.length ≤ 10,000
- sets contains only the letters A to Z
- 0 ≤ rest ≤ 100
Start with brute force
Simulate slot by slot, and at each slot try every group that is allowed right now, plus resting, exploring all orders to find the shortest. The number of orders grows exponentially with the number of sets, so even 30 sets is out of reach.
A cheaper simulation picks, at each slot, the allowed group with the most sets left. That is correct, but it builds the whole schedule slot by slot, which is far more work than needed: the answer depends only on how many sets the busiest groups have.
Hints
0 of 4 shown- Hint 1
In the first example, forget C for a moment and place only the three L sets. How many slots do they force, no matter what else is on the card?
- Hint 2
The group with the most sets builds a frame. If it has
msets, they needm - 1gaps ofrestslots each between them. The other sets go into those gaps. What happens when another group has just as many sets as the biggest one? - Hint 3
Every group that ties for the most sets adds one slot at the very end of the frame. So the frame is
(m - 1) × (rest + 1) + k, wherekis the number of tied groups. When could the real answer be larger than the frame? - Hint 4
Count sets per group. Let
mbe the largest count andkhow many groups have it. If the other sets overflow the gaps, you never need to rest at all, and the answer is just the number of sets. Returnmax(sets.length, (m - 1) × (rest + 1) + k).
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The group with the most sets is the bottleneck. Lay its sets out as early as the rule allows, and you get a frame: m - 1 blocks of rest + 1 slots, then the last set. Groups tied for the most sets also need a slot after the last block. Every other set fits into the gaps, because each has fewer than m sets and can be spread across different blocks.
Trace "AAABBBCCD" with rest 1. Counts: A 3, B 3, C 2, D 1. So m = 3 and k = 2 (A and B tie).
- Frame:
(3 - 1) × (1 + 1) + 2 = 6slots:A B | A B | A B. - C, C and D still need places. The frame has no empty slots left, but you can widen any block:
A B C | A B C | A B D. Widening never breaks the rule, it only puts more slots between equal groups. To place leftovers safely, deal them one group at a time, one set per block, cycling through the blocks. Two sets of the same group then always land in different blocks, at least a whole block apart. - No rest slots are needed, so the answer is the number of sets, 9. That is
max(9, 6).
Two answers to keep apart: when the gaps are not filled, rests are unavoidable and the frame size is the answer; when the other sets overflow the gaps, you never rest, and the answer is simply the number of sets. The max covers both.
function fewestSlots(sets, rest) {
if (sets.length === 0) return 0;
const count = {};
for (const g of sets) count[g] = (count[g] || 0) + 1;
const counts = Object.values(count);
const most = Math.max(...counts);
const tied = counts.filter(c => c === most).length;
// The busiest group(s) build a frame; other sets fill its gaps.
const frame = (most - 1) * (rest + 1) + tied;
return Math.max(sets.length, frame);
}from collections import Counter
def fewest_slots(sets, rest):
if not sets:
return 0
counts = Counter(sets).values()
most = max(counts)
tied = sum(1 for c in counts if c == most)
# The busiest group(s) build a frame; other sets fill its gaps.
frame = (most - 1) * (rest + 1) + tied
return max(len(sets), frame)Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.