LeetCode 763 - Partition Labels
The problem is asking us to partition a string s into as many contiguous parts as possible such that no letter appears in more than one part. In other words, each character in the string should be confined to a single segment.
Difficulty: 🟡 Medium
Topics: Hash Table, Two Pointers, String, Greedy
Solution
Problem Understanding
The problem is asking us to partition a string s into as many contiguous parts as possible such that no letter appears in more than one part. In other words, each character in the string should be confined to a single segment. After partitioning, concatenating all the segments in order should reproduce the original string exactly. The input is a string of lowercase English letters with length between 1 and 500. The output is a list of integers, where each integer represents the length of a partitioned segment.
The key challenge is to ensure that each character appears in at most one segment. A naive approach might attempt to generate all possible partitions and check for validity, but this would be computationally infeasible for the upper bound of 500 characters.
Important edge cases include strings with all identical characters, strings with no repeating characters, and strings where all characters are unique except for a single repeated character near the end.
Approaches
Brute Force
The brute force approach would try to explore every possible way to split the string and validate whether each partition satisfies the rule that each letter occurs in only one segment. This requires tracking all letters in each segment and comparing them with the remaining string. While it is correct, it is highly inefficient because the number of ways to split a string grows exponentially with its length.
Optimal Approach
The optimal approach relies on a greedy strategy using two pointers. First, record the last occurrence of each character in a hash map. Then iterate through the string, maintaining a running end index of the current partition, which is the farthest last occurrence of any character seen so far. When the current index reaches this running end, we know we can safely partition here because no character in this segment will appear later. This ensures that each character is confined to one segment and produces the maximum number of partitions.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n * n) | O(n) | Tries all possible splits and validates each partition, infeasible for large n |
| Optimal | O(n) | O(26) ~ O(1) | Greedy approach using hash map to track last occurrences, linear scan |
Algorithm Walkthrough
- Create a hash map to store the last index of each character in the string. This allows us to know the farthest point a character can appear.
- Initialize two pointers:
startfor the beginning of the current partition andendto track the farthest last occurrence of any character in the current partition. - Iterate through the string character by character. For each character, update
endto the maximum of its current value and the last occurrence of this character. - If the current index equals
end, it means we have reached the end of the current partition. Append the size of this partition (end - start + 1) to the result list. - Move
starttoindex + 1to begin the next partition. - Continue until the entire string is processed.
Why it works: The greedy approach guarantees that each partition contains all occurrences of its characters. The invariant is that end always represents the last index of any character seen in the current partition. Once the current index reaches end, no characters from this partition appear later, ensuring correctness.
Python Solution
from typing import List
class Solution:
def partitionLabels(self, s: str) -> List[int]:
# Step 1: record the last occurrence of each character
last_occurrence = {char: idx for idx, char in enumerate(s)}
partitions = []
start, end = 0, 0
# Step 2: iterate over the string
for idx, char in enumerate(s):
# Step 3: update the end to the farthest last occurrence of any character seen
end = max(end, last_occurrence[char])
# Step 4: if current index is end, close partition
if idx == end:
partitions.append(end - start + 1)
start = idx + 1
return partitions
Implementation Explanation: First, a dictionary last_occurrence maps each character to its last index. As we iterate, we extend end to cover all characters seen so far. When the current index reaches end, we finalize the partition and record its length. start is then updated to begin a new partition.
Go Solution
func partitionLabels(s string) []int {
lastOccurrence := make(map[byte]int)
for i := 0; i < len(s); i++ {
lastOccurrence[s[i]] = i
}
var partitions []int
start, end := 0, 0
for i := 0; i < len(s); i++ {
if lastOccurrence[s[i]] > end {
end = lastOccurrence[s[i]]
}
if i == end {
partitions = append(partitions, end-start+1)
start = i + 1
}
}
return partitions
}
Go-Specific Notes: Go uses byte for characters in a string. The map lastOccurrence keeps the last index of each character. Slice partitions is used to dynamically store the partition sizes, similar to a Python list.
Worked Examples
Example 1: "ababcbacadefegdehijhklij"
| idx | char | last_occurrence[char] | end | start | partitions |
|---|---|---|---|---|---|
| 0 | a | 8 | 8 | 0 | [] |
| 1 | b | 5 | 8 | 0 | [] |
| 2 | a | 8 | 8 | 0 | [] |
| 3 | b | 5 | 8 | 0 | [] |
| 4 | c | 7 | 8 | 0 | [] |
| 5 | b | 5 | 8 | 0 | [] |
| 6 | a | 8 | 8 | 0 | [] |
| 7 | c | 7 | 8 | 0 | [] |
| 8 | a | 8 | 8 | 0 | [9] |
| 9 | d | 14 | 14 | 9 | [] |
| 10 | e | 15 | 15 | 9 | [] |
| 11 | f | 11 | 15 | 9 | [] |
| 12 | e | 15 | 15 | 9 | [] |
| 13 | g | 13 | 15 | 9 | [] |
| 14 | d | 14 | 15 | 9 | [] |
| 15 | e | 15 | 15 | 9 | [7] |
| 16 | h | 19 | 19 | 16 | [] |
| 17 | i | 22 | 22 | 16 | [] |
| 18 | j | 23 | 23 | 16 | [] |
| 19 | h | 19 | 23 | 16 | [] |
| 20 | k | 20 | 23 | 16 | [] |
| 21 | l | 21 | 23 | 16 | [] |
| 22 | i | 22 | 23 | 16 | [] |
| 23 | j | 23 | 23 | 16 | [8] |
Result: [9,7,8]
Example 2: "eccbbbbdec"
All characters' last occurrence is within the string, so only one partition: [10].
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Single pass to record last occurrences and another pass to partition the string |
| Space | O(26) ~ O(1) | Hash map for 26 letters only |
The linear time complexity comes from iterating through the string twice. Space complexity is constant since there are only 26 lowercase English letters.
Test Cases
# Basic examples
assert Solution().partitionLabels("ababcbacadefegdehijhklij") == [9,7,8] # Example 1
assert Solution().partitionLabels("eccbbbbdec") == [10] # Example 2
# Edge cases
assert Solution().partitionLabels("a") == [1] # Single character
assert Solution().partitionLabels("aaaa") == [4] # All same character
assert Solution().partitionLabels("abcd") == [1,1,1,1] # All unique characters
# Mixed repeats
assert Solution().partitionLabels("abac") == [3,1] # 'a' repeats
assert Solution().partitionLabels("abcdecf") == [6,1] # last 'f' separate
| Test | Why |
|---|---|
| "ababcbacadefegdehijhklij" | Validates multiple partitions with overlapping characters |
| "eccbbbbdec" | Validates single partition when characters spread across the string |
| "a" | Minimum input size |
| "aaaa" | All characters identical |
| "abcd" | All unique characters |
| "abac" | Overlapping letters require merging partitions |
| "abcdecf" | Ensures last partition captures non-overlapping character |
Edge Cases
Single character string: This tests the minimum input size. The algorithm correctly returns [1] because the only character forms a valid partition by itself.
All identical characters: For a string