—
i
Partition a string into as many parts as possible so that each letter appears in at most one part. Two linear passes do it: first record every character's last occurrence, then sweep with a greedy window — extend the window whenever the current char's last index exceeds the window end, and cut as soon as you reach that end.
Given a string s, partition it into as many substrings as possible so that each letter appears in exactly one part. Return a list of the partition sizes.
Example: s = "ababcbacadefegdehijhklij"
The answer is [9, 7, 8]. The partitions are "ababcbaca" (9), "defegde" (7), and "hijhklij" (8). Every letter in each piece never appears in any other piece.
c, you must include every occurrence of c. So a partition starting at start must extend at least as far as last[c] for each character c it encounters. Scan left to right, grow the right boundary greedily, and cut the moment you arrive at that boundary — that is the earliest legal cut.s once and store last[c] = i for every character c at index i. Overwriting is fine — the final write is always the rightmost occurrence.start = 0, end = 0.i: end = Math.max(end, last[s[i]]). This ensures the current window covers all occurrences of every character seen so far.i === end. We have just consumed every character that was forced into this partition. Record end − start + 1, then advance start = end + 1.end to start after a cut (instead of start = end + 1). The variable end naturally becomes the new start minus one at each cut, so the correct idiom is just start = end + 1; the next iteration of the loop immediately overwrites end via the Math.max.Space is O(1) for lowercase a–z (26-slot array) or O(k) for k distinct characters with a Map. The result array is O(p) where p is the number of partitions, which is at most O(n) but typically much smaller.
1function partitionLabels(s: string): number[] {2 // Pass 1: record the last index of every character3▶ const last: Record<string, number> = {};4▶ for (let i = 0; i < s.length; i++) {5▶ last[s[i]] = i;6 }78 // Pass 2: sweep and cut when we reach the partition boundary9 const result: number[] = [];10 let start = 0;11 let end = 0;1213 for (let i = 0; i < s.length; i++) {14 end = Math.max(end, last[s[i]]); // stretch end to cover this char's last occurrence15 if (i === end) { // we consumed everything this partition can reference16 result.push(end - start + 1);17 start = end + 1;18 }19 }20 return result;21}
function partitionLabels(s: string): number[] {
// Pass 1: record the last index of every character
const last: Record<string, number> = {};
for (let i = 0; i < s.length; i++) {
last[s[i]] = i;
}
// Pass 2: sweep and cut when we reach the partition boundary
const result: number[] = [];
let start = 0;
let end = 0;
for (let i = 0; i < s.length; i++) {
end = Math.max(end, last[s[i]]); // stretch end to cover this char's last occurrence
if (i === end) { // we consumed everything this partition can reference
result.push(end - start + 1);
start = end + 1;
}
}
return result;
}last. Because we overwrite on every visit, the final value is always the largest index for that character.start is where the current partition begins. end is the minimum right boundary we must reach before we can cut — it starts equal to start.end = Math.max(end, last[s[i]])ensures the window stretches far enough to include every occurrence of the current character. This is the core greedy decision: we can never cut before last[s[i]].i === end, all characters in [start..end] have their last occurrences inside this range — a legal partition. Record its size and advance start.s. O(1) extra space for the 26-entry last map (or O(k) for k distinct chars with a Map).result.push(end - start + 1) with result.push(s.slice(start, end + 1)).last storage from 26 to 52 slots, or switch to a Map<string, number>.[first[c], last[c]]; the partitions are exactly the merged non-overlapping intervals of those character intervals, processed greedily from left to right.function partitionLabels(s: string): number[] {
// Pass 1: record the last index of every character
const last: Record<string, number> = {};
for (let i = 0; i < s.length; i++) {
last[s[i]] = i;
}
// Pass 2: sweep and cut when we reach the partition boundary
const result: number[] = [];
let start = 0;
let end = 0;
for (let i = 0; i < s.length; i++) {
end = Math.max(end, last[s[i]]); // stretch end to cover this char's last occurrence
if (i === end) { // we consumed everything this partition can reference
result.push(end - start + 1);
start = end + 1;
}
}
return result;
}s. O(1) extra space for the 26-entry last map (or O(k) for k distinct chars with a Map).Start a partition at start, then repeatedly extend its end: whenever a character inside [start..end] also appears somewhere later than end, push endout to that later index and re-scan. Cut once the window is stable.
function partitionLabels(s: string): number[] {
const result: number[] = [];
let start = 0;
while (start < s.length) {
let end = start;
let i = start;
// Keep widening [start..end] until no char inside it appears past end.
while (i <= end) {
// Does s[i] occur anywhere after the current end?
for (let j = s.length - 1; j > end; j--) {
if (s[j] === s[i]) {
end = j; // stretch the window to cover this occurrence
break;
}
}
i++;
}
result.push(end - start + 1);
start = end + 1;
}
return result;
}| "each letter in at most one part" | last-index map + greedy window |
| partition / split string with character-range constraint | last[c] extension + cut at i===end |
| minimize number of partitions or maximize cuts | greedy interval merging |
| interval-merge / non-overlapping intervals variant | sort by start, merge by extending end |
const last: Record<string, number> = {};
for (let i = 0; i < s.length; i++) last[s[i]] = i;
const result: number[] = [];
let start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
end = Math.max(end, last[s[i]]);
if (i === end) {
result.push(end - start + 1);
start = end + 1;
}
}
return result;s = "ababcbacadefegdehijhklij"?s = "ababcbacadefegdehijhklij". What is the first partition size?s = "eccbbbbdec", what does the algorithm return?