Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Close a segment only after every letter ends: The Letter Territories.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Greedy last-occurrence partitioning matches the clues
- 2Keep this true after every move: end is the farthest last occurrence of every character inside the open partition
- 3Reach the result within O(n)
Rules and pressure
- Target cost: O(n)
- State rule: end is the farthest last occurrence of every character inside the open partition
New words in this mission
Open a term for a plain-language explanation.partition or shard+
One slice of a larger dataset or workload. Splitting work raises capacity, but cross-slice operations become harder.
Lesson 1 of 3
Live algorithm trace
Greedy last-occurrence partitioning
Complete execution1 of 6
Record the final position of each character before choosing any cut.
1
record each character's last index2
start = end = 03
for i through the string4
end = max(end, last[s[i]])5
if i == end: emit end - start + 16
start = i + 17
return sizeslastA = 8lastB = 5lastC = 7
Truth to preserve / Cost target
Truth to preserve
end is the farthest last occurrence of every character inside the open partition
Cost target
O(n)
A partition beginning at start must extend through the last occurrence of every character it encounters. Close it at the first index that reaches this expanding boundary.
Your call · What should guide every step of this algorithm?