⚡Flashcard Drill➔
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

  1. Precompute the last occurrence index of every character.
  2. Scan left to right while maintaining the current partition's end, initially the last occurrence of the first character.
  3. At each index, extend end = max(end, last[c]) so that no character is split across partitions.
  4. 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 is end - 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems