1. Last index map
Record the last position each character appears.
last[s[i]] = iTyporithm · medium
Partition Labels
▷ Interactive algorithm labpartition-labelsgreedylast-occurrenceextend-endgreedy-choice
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Partition Labels
Greedy
Map each character's last index, then grow a partition until the scan reaches its farthest required end.
Each character must live entirely within one partition, so a partition has to reach every character's last occurrence.
First record the last index of every character.
Then scan, stretching the current end to the farthest last-index seen; close the partition when i meets end.
Preparing algorithm lab…
01
Precompute last index per character.
02
Extend end to last[s[i]].
03
Close when i === end.
function partitionLabels(s) {
const last = {};
for (let i = 0; i < s.length; i += 1) {
last[s[i]] = i;
}
const result = [];
let start = 0;
let end = 0;
for (let i = 0; i < s.length; i += 1) {
end = Math.max(end, last[s[i]]);
if (i === end) {
result.push(end - start + 1);
start = i + 1;
}
}
return result;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Stretch the cut
The partition must reach the last occurrence of every character inside it.
end = Math.max(end, last[s[i]])3. Close partition
When the scan reaches the current end, the partition is complete.
if (i === end)4. Record size
Save the partition length and start the next one.
result.push(end - start + 1)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.