LeetCode · #763

Partition Labels Solution

Partition a string into as many parts as possible so each letter appears in at most one part. Return the list of part sizes.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #763

🏗️

Pattern

Greedy — last occurrence + merge

Given a string s, partition it into as many parts as possible so that each letter appears in at most one part. Return a list of integers representing the size of each part.

Example

Input: s = "ababcbacadefegdehijhklij" Output: [9, 7, 8]
// "ababcbaca" (9), "defegde" (7), "hijhklij" (8)

Constraints

• 1 ≤ s.length ≤ 500 • s consists of lowercase English letters

Section Two · Approach 1

Brute Force — O(n²)

For each partition start, scan forward to find the last occurrence of each character encountered. Extend the partition until all characters are contained.

Problem: Rescanning for last occurrences is O(n) per partition. Pre-compute last occurrences in O(n), then do a single greedy pass.

Java — Pre-scan but O(n²) partition

 class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> res = new ArrayList<>();
int start = 0;
while (start < s.length()) {
int end = s.lastIndexOf(s.charAt(start)); // O(n) for (int k = start; k < end; k++)
                end = Math.max(end, s.lastIndexOf(s.charAt(k))); // O(n)
res.add(end - start + 1);
            start = end + 1;
        }
return res;
    }
}

Python — Brute

 class Solution:
def partitionLabels(self, s: str) -> list[int]:
        res, start = [], 0 while start < len(s):
            end = s.rindex(s[start])
            k = start
while k < end:
                end = max(end, s.rindex(s[k]))
                k += 1
res.append(end - start + 1)
            start = end + 1 return res

Section Three · Approach 2

Greedy — O(n) time, O(1) space

Pre-compute last[c] = last index of each character. Then scan left to right, extending each partition's end to max(end, last[s[i]]). When i == end, the partition is complete.

💡 Mental model: Imagine each letter is a rubber band stretched from its first occurrence to its last. You start at the left edge and walk right. Each letter you encounter forces you to extend your current partition to at least the end of its rubber band. When you reach the farthest rubber band end, cut — that's a partition boundary. All rubber bands within the partition are fully contained.

Algorithm

Build last[26]: last occurrence of each letter.
start = 0, end = 0. For each i:
end = max(end, last[s[i]]). If i == end: add end - start + 1 to result, start = i + 1.

🎯 When to recognize this pattern: "Partition string/array into segments where no element appears in multiple segments." The signal: constraint-based partitioning. Pre-compute ranges, then merge overlapping ranges greedily — similar to interval merging (LC 56).

Section Four · Trace

Visual Walkthrough

Trace for s = "ababcbacadefegdehijhklij".

Partition Labels — Last Occurrence + Greedy Sweep

Section Five · Implementation

Code — Java & Python

Java — Greedy

 import java.util.*;
class Solution {
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
for (int i = 0; i < s.length(); i++)
            last[s.charAt(i) - 'a'] = i;
List<Integer> res = new ArrayList<>();
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
if (i == end) {
                res.add(end - start + 1);
                start = i + 1;
            }
        }
return res;
    }
}

Python — Greedy

 class Solution:
def partitionLabels(self, s: str) -> list[int]:
        last = {c: i for i, c in enumerate(s)}
        res, start, end = [], 0, 0 for i, c in enumerate(s):
            end = max(end, last[c])
if i == end:
                res.append(end - start + 1)
                start = i + 1 return res

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute force	O(n²)	O(1)	Rescan for each partition
Greedy ← optimal	O(n)	O(1)	26-char array is constant space; two passes

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single char	`"a"`	One partition of size 1.
All unique	`"abcde"`	Each char appears once → five partitions of size 1: [1,1,1,1,1].
All same	`"aaaa"`	One partition of size 4.
Nested ranges	`"abacd"`	'a' spans 0-2, 'b' at 1. Partition 1: "aba" (3). Then "c" (1), "d" (1).

⚠ Common Mistake: Using the first occurrence instead of the last occurrence. First occurrence tells you where a character starts, but the partition must extend to where it ends. Always pre-compute last[c] and extend to the farthest last occurrence seen so far.

← Back to Greedy problems

LearningTree

LC 763 · Partition Labels — Solution & Explanation | DSA Guide