Parcel Line Into Trucks
At a sorting depot, parcels come off a conveyor belt in a fixed order. Each parcel is stamped with a one-letter code for its destination town. The loaders fill trucks straight from the belt: the first few parcels go on truck 1, the next few on truck 2, and so on, without reordering anything.
Each town should be served by exactly one truck, so all parcels for a town must end up on the same truck. Within that rule, the depot wants as many trucks as possible, because smaller loads leave sooner.
Your task
Write truckLoads(tags). tags is a string of lowercase letters, one per parcel, in belt order. Cut it into as many consecutive pieces as possible so that every letter appears in only one piece. Return the lengths of the pieces, in order.
An empty string returns an empty list.
truckLoads(tags: string) → int[]
Examples
tags = "kbkmzmqq"
[3, 3, 2]
The k parcels sit at positions 0 and 2, so the first truck takes at least "kbk". Nothing in "kbk" appears later, so cut there. Next, "mzm" holds both m parcels, then "qq". Three trucks: 3, 3 and 2 parcels.
tags = "abccbadd"
[6, 2]
The first a is at position 0 and the last a at position 5, so the first truck must take positions 0 to 5, which also covers every b and c. Then "dd" is the second truck. Cutting after "abc" would split the a parcels across two trucks.
Constraints
- 0 ≤ tags.length ≤ 10,000
- tags contains only the letters a to z
Start with brute force
For every possible cut position, check whether the letters on the left and the letters on the right are disjoint. Every such position is a safe cut, and cutting at all of them gives the most pieces. Building the two letter sets at each position costs O(n), so this is O(n²) overall: around 100 million steps for 10,000 parcels.
The repeated work is rebuilding the sets. Knowing just each letter's last position answers the same question as you walk.
Hints
0 of 4 shown- Hint 1
Look at the first parcel in the second example, an a. What is the shortest the first truck could possibly be?
- Hint 2
The first truck must reach at least the last a. But the letters it picks up on the way have last positions too. When can you finally be sure the truck is complete?
- Hint 3
First record the last position of every letter. Then walk the belt and keep
end, the farthest last-position of any letter in the current truck so far. - Hint 4
Walk with a
startand anend. At each positioni, setend = max(end, last[tags[i]]). Wheni === end, every letter in this piece is finished: recordi - start + 1and start the next piece ati + 1.
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
Each letter is really an interval: from its first parcel to its last. A truck boundary can only fall where no interval crosses it. Cut as early as you safely can, and you get the most trucks.
Trace "kbkmzmqq". Last positions: k → 2, b → 1, m → 5, z → 4, q → 7.
- i = 0, k:
end = 2. - i = 1, b:
end = max(2, 1) = 2. - i = 2, k:
end = 2, and i equals end. Cut: a truck of 3. Next start is 3. - i = 3, m:
end = 5. i = 4, z: still 5. i = 5, m: i equals end. Truck of 3. - i = 6, q:
end = 7. i = 7: cut. Truck of 2. Answer:[3, 3, 2].
The common slip is cutting when the current letter is finished. In "abab" the a at position 2 is the last a, but the b from position 1 still has a parcel at 3. Tracking the max across the whole truck fixes that.
function truckLoads(tags) {
const last = {}; // letter -> last position on the belt
for (let i = 0; i < tags.length; i++) last[tags[i]] = i;
const loads = [];
let start = 0, end = 0;
for (let i = 0; i < tags.length; i++) {
end = Math.max(end, last[tags[i]]); // this truck must reach here
if (i === end) { // every letter so far is finished
loads.push(i - start + 1);
start = i + 1;
}
}
return loads;
}def truck_loads(tags):
last = {c: i for i, c in enumerate(tags)} # letter -> last position
loads = []
start = end = 0
for i, c in enumerate(tags):
end = max(end, last[c]) # this truck must reach here
if i == end: # every letter so far is finished
loads.append(i - start + 1)
start = i + 1
return loadsRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.