Skip to content

Volume ITechnology

4.26.7 — Partition Labels ​

LeetCode 763 · Medium

The problem ​

Split the string into as many parts as possible, so that each letter appears in at most one part. Return the sizes of the parts.

Restating the Problem: You have a string of lowercase English letters. You want to chop it into contiguous substrings (partitions). The rule is: if a letter (like 'a') appears in one partition, all other 'a's in the string must also be in that exact same partition. You want to make as many partitions as possible.

  • Constraints to note: The string length is up to 500, which is small, but an O(n) solution is straightforward and expected. The string contains only lowercase English letters, meaning we have a fixed alphabet size of 26.
s = "ababcbacadefegdehijhklij"   →  [9,7,8]
    "ababcbaca" | "defegde" | "hijhklij"

The brute force, and where it wastes work ​

You could try all possible partitions. For a string of length n, there are n-1 places to put a cut, meaning 2^{n-1} possible ways to partition the string. For each partitioning, you'd check if any letter crosses boundaries. This O(2^n) approach is incredibly slow and completely unnecessary.

The pattern ​

A part cannot end before the last occurrence of every letter it contains. So:

Precompute the last index of each letter. Then sweep, extending the current part's end to cover every letter you meet, and cut as soon as you reach that end.

Two passes. The first builds a 26-entry table; the second is one linear sweep.

Why this is optimal. The part must extend at least to the furthest last-occurrence of anything inside it, so cutting earlier is impossible. And cutting the moment you can is what maximises the number of parts. There is no choice — the boundary is forced, exactly like 4.26.5 Hand of Straights.

The solution ​

python
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)}       # (1) last index of each letter

        result = []  # (2)
        start = end = 0  # (3)

        for i, c in enumerate(s):  # (4)
            end = max(end, last[c])                  # (5) this part must reach here

            if i == end:                             # (6) nothing inside reaches further
                result.append(end - start + 1)  # (7)
                start = i + 1  # (8)

        return result
ts
function partitionLabels(s: string): number[] {
  const last = new Map<string, number>();  // (1)
  for (let i = 0; i < s.length; i++) last.set(s[i], i);

  const result: number[] = [];  // (2)
  let start = 0, end = 0;  // (3)

  for (let i = 0; i < s.length; i++) {  // (4)
    end = Math.max(end, last.get(s[i])!);  // (5)

    if (i === end) {  // (6)
      result.push(end - start + 1);  // (7)
      start = i + 1;  // (8)
    }
  }

  return result;
}

Line by line ​

(1) The last position of every letter in the string. Every copy of a letter must be in the same part, so a part containing a letter must stretch at least to that letter's last position.

(2) The sizes of the parts.

(3) The current part starts at start, and must stretch at least to end.

(4) Walk the string.

(5) This letter's last copy is at last[c], so the part must reach at least there.

(6) We have reached the furthest point any letter in this part needs. No letter seen so far appears again later, so the part can end here.

(7) Record its size, and

(8) start the next part at the next position.

{c: i for i, c in enumerate(s)} keeps the last index of each letter, because later assignments overwrite earlier ones. That one line is the whole precomputation. A dictionary built this way naturally keeps the last value for each key.

end = max(end, last[c]) is the extension. Every letter you meet drags the boundary out to wherever that letter last appears.

i == end is the cut. You have walked to the furthest point anything in this part requires, so nothing inside it appears later. Cut here.

Code Walkthrough:

  • Precomputation: We first iterate through the string to build a dictionary/map last that records the final index where each character appears.
  • Initialization: We set start = 0 and end = 0 to track the boundaries of our current partition.
  • Iterating for Cuts: We loop through the string again with index i.
  • Extending the Boundary: At each character c, we check last[c]. If this character appears later in the string than our current end, we must extend end to last[c].
  • Making a Cut: If our current index i catches up to end (i == end), it means we've passed the last occurrence of every character we've seen so far in this partition. We can safely make a cut. We record the size end - start + 1 and begin a new partition at start = i + 1.

end - start + 1 is the part's length, with the +1 because both ends are included.

Trace ​

"ababcbacadefegdehijhklij"

Last occurrences: a at 8, b at 5, c at 7, d at 14, e at 15, f at 11, g at 13, h at 19, i at 22, j at 23, k at 20, l at 21.

icharend aftercut?
0a8no
1b8no
4c8no
8a8yes → part of length 9
9d14no
11f14no
13g15 (from e at 11)no
15e15yes → length 7
16…h i j k l23cut at 23 → length 8

[9, 7, 8] ✓.

Edge cases ​

  • Every letter different. Every letter is its own part.
  • One letter repeated, like "aaaa". One part.
  • The first and last letters are the same. The whole string is one part.

Complexity ​

O(n) time — two passes. O(1) space, since the table holds at most 26 letters.

  • Time Complexity: O(n). We pass through the string of length n exactly twice: once to find the last occurrences and once to determine the partitions.
  • Space Complexity: O(1). The hash map stores at most 26 key-value pairs (one for each lowercase English letter), which uses a constant amount of extra memory.

This is an interval problem in disguise ​

Each letter defines an interval from its first to its last occurrence. Two letters must be in the same part exactly when their intervals overlap. So the parts are the connected groups of overlapping intervals — which is Merge Intervals (4.27.2).

The sweep above is merging those intervals without ever building them, because walking the string visits them in order of their start already.

Saying this out loud is the strongest thing you can do on this problem. It shows you see the structure rather than the trick, and it is why this problem sits between the greedy and interval chapters.

Where this goes next ​

  • Merge Intervals — the same merging, stated explicitly. 4.27.2.
  • Jump Game II — the same "extend the reach, then cut at the boundary" sweep. 4.26.3. These two problems have almost identical code but completely different stories.
  • Video Stitching, Minimum Taps — interval covering with the same reach-extension loop.

What the interviewer will push on ​

"Why must a part reach the last occurrence of every letter inside it?" Otherwise that letter appears in two parts.

"Why is cutting as early as possible optimal?" The boundary is forced, and cutting at the first legal point maximises the count.

"How do you get the last occurrences?" One pass, letting later writes overwrite earlier ones.

"What is the space complexity?" O(1) — 26 letters, fixed. Say why it is constant rather than O(n).

"Is this related to any other problem?" Merge Intervals, with one interval per letter.

One thing to volunteer: the interval framing, and the fact that this is Jump Game II's loop with a different meaning. Two connections in one sentence each, and both show the pattern rather than the puzzle.

Next: 4.26.8 Valid Parenthesis String — the last greedy, where you track a range of possibilities instead of one number.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet