NeetCode #794LC-763MediumGreedyNC 150NC 250
← Back to All Problems#794 · #763 · Partition Labels(划分字母区间)
📌 Problem Statement & Constraints
You are given a string
s. Partition it into as many parts as possible so that each letter appears in at most one part, and return a list of the sizes of these parts. Constraints: 1 <= s.length <= 500, s consists of lowercase English letters.💡 Core Algorithmic Approaches
- Precompute the last occurrence index of every character.
- Scan left to right while maintaining the current partition's
end, initially the last occurrence of the first character. - At each index, extend
end = max(end, last[c])so that no character is split across partitions. - When the scan index reaches
end, the partition is closed; record its size and start a new one.
💻 Benchmark Python3 Implementation
class Solution:
def partitionLabels(self, s: str) -> List[int]:
last = {c: i for i, c in enumerate(s)}
res = []
start = 0
end = 0
for i, c in enumerate(s):
end = max(end, last[c]) # keep the partition whole
if i == end: # all letters closed inside
res.append(end - start + 1)
start = i + 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass to build last, one to partition.
💾 Space Complexity
O(1) beyond the output: at most 26 last-occurrence entries.
⚠️ Interview Pitfalls & Follow-ups
- Using the first occurrence instead of the last: a character appearing later would be split across parts.
- Not taking the maximum of
end: forgetting to extend the boundary when a character reaches further right. - Recording the length as
end - start: the inclusive length isend - start + 1. - Greedily closing a part whenever a character repeats: parts must end exactly where every enclosed character has no later occurrence.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.