Partition Labels solution and explanation
Infosys
Google
9 more videos on this problem
Partition Labels - Leetcode 763 - PythonNeetCode · 14:29 · 67K views
LeetCode 763. Partition Labels (Solution Explained)Nick White · 12:56 · 17K views
Partition Labels (LeetCode 763) | Solution with animations and examples | Study AlgorithmsNikhil Lohia · 15:55 · 10K views
Partition Labels - Leetcode 763 - PythonNeetCodeIO · 14:29 · 8K views
[Java] Leetcode 763. Partition Labels [Two Pointers #7]Eric Programming · 9:54 · 3K views
partition labels | partition labels leetcode | leetcode 763 | two pointer | leetcode septemberNaresh Gupta · 7:50 · 2K views
Partition Labels | Leet code 763 | Theory explained + Python codeSai Anish Malla · 12:18 · 1K views
Partition Labels Leetcode | Leetcode 763 | Leetcode September ChallengeCode Bashers · 13:59 · 966 views
Partition Labels | LeetCode 763 Greedy ExplainedDestination FAANG · 10:34 · 488 views
Partition Labels - LeetCode 763 - Coding Interview QuestionsOne Code Man · 4:21 · 417 views
The problem
You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.
Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.
Return a list of integers representing the size of these parts.
Example 1:
Input: s = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.
Example 2:
Input: s = "eccbbbbdec" Output: [10]
Constraints:
1 <= s.length <= 500sconsists of lowercase English letters.
Approach overview
Problem Overview: Given a string s, split it into as many parts as possible so that each letter appears in at most one partition. After splitting, concatenating all parts must still produce the original string. The goal is to return the size of each partition.
Approach 1: Greedy with Last Occurrence (O(n) time, O(1) space)
This is the optimal approach and relies on a simple greedy observation: a partition cannot end until you pass the last occurrence of every character currently inside it. First iterate through the string and store the last index where each character appears using a small lookup array or hash table. Then scan the string again while tracking the farthest last index among characters seen so far. When the current index matches that boundary, you can safely close the partition because all characters inside it will not appear later. This technique works well because the alphabet size is fixed (26 lowercase letters), giving O(1) space and O(n) total time.
Approach 2: Two-Pass Trick (O(n) time, O(1) space)
Another way to reason about the problem is to track how many times each character still appears ahead in the string. In the first pass, count frequencies of all characters. In the second pass, iterate through the string while decrementing the remaining count for each character. Maintain a set or counter of "active" characters currently present in the partition. When the remaining frequency of a character drops to zero, it means that character will not appear later. Once all active characters reach zero remaining occurrences, the current segment becomes a valid partition. This approach also runs in linear time and relies heavily on string traversal and counting logic.
Recommended for interviews: Interviewers typically expect the greedy last-occurrence method. It demonstrates the ability to recognize interval boundaries and apply a greedy strategy. Implementing the first pass to record last indices and the second pass to expand the partition boundary is straightforward and clearly shows optimal O(n) reasoning. The two-pass frequency trick is also valid but slightly less common in interview discussions.
Approach 1: Greedy Method with Last Occurrence
This approach uses a greedy method where we determine the possible endpoints of each partition by finding the last occurrence of each character. As we iterate through the string, we expand the end of the current partition to the maximum last occurrence index of all characters seen so far. The current partition ends once the current index matches this endpoint.
def partitionLabels(S):
last = {char: i for i, char in enumerate(S)}
j = anchor = 0
result = []
for i, char in enumerate(S):
j = max(j, last[char])
if i == j:
result.append(i - anchor + 1)
anchor = i + 1
return resultimport java.util.ArrayList;
import java.util.List;
public class PartitionLabels {
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
int length = s.length();
for (int i = 0; i < length; i++) {
last[s.charAt(i) - 'a'] = i;
}
List<Integer> result = new ArrayList<>();
int start = 0, end = 0;
for (int i = 0; i < length; i++) {
end = Math.max(end, last[s.charAt(i) - 'a']);
if (i == end) {
result.add(end - start + 1);
start = i + 1;
}
}
return result;
}
}#include <vector>
#include <string>
using namespace std;
vector<int> partitionLabels(string s) {
vector<int> last(26, 0);
int len = s.size();
for (int i = 0; i < len; ++i) {
last[s[i] - 'a'] = i;
}
vector<int> result;
int start = 0, end = 0;
for (int i = 0; i < len; ++i) {
end = max(end, last[s[i] - 'a']);
if (i == end) {
result.push_back(end - start + 1);
start = i + 1;
}
}
return result;
}var partitionLabels = function(s) {
let last = {};
for (let i = 0; i < s.length; i++) {
last[s[i]] = i;
}
let result = [];
let start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
end = Math.max(end, last[s[i]]);
if (i === end) {
result.push(end - start + 1);
start = i + 1;
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
int* partitionLabels(char* s, int* returnSize) {
int last[26] = {0};
int length = strlen(s);
// Record the last occurrence of each character
for (int i = 0; i < length; i++) {
last[s[i] - 'a'] = i;
}
int* result = (int*)malloc(length * sizeof(int));
int resultIndex = 0;
int start = 0, end = 0;
for (int i = 0; i < length; i++) {
end = (end > last[s[i] - 'a']) ? end : last[s[i] - 'a'];
if (i == end) {
result[resultIndex++] = end - start + 1;
start = i + 1;
}
}
*returnSize = resultIndex;
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> PartitionLabels(string s) {
int[] last = new int[26];
for (int i = 0; i < s.Length; i++) {
last[s[i] - 'a'] = i;
}
List<int> result = new List<int>();
int start = 0, end = 0;
for (int i = 0; i < s.Length; i++) {
end = Math.Max(end, last[s[i] - 'a']);
if (i == end) {
result.Add(end - start + 1);
start = i + 1;
}
}
return result;
}
}This Python solution stores the last occurrence of each character in a dictionary. It iterates through the string and determines the end of each partition based on the maximum last occurrence index of characters seen. It keeps track of partition sizes using a list.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since we only require a fixed number of extra variables.
Approach 2: Two-Pass Trick
Another approach involves performing two passes over the string. The first pass is used to collect the rightmost occurrence of each character, and in the second pass, we calculate the sizes of partitions while maintaining the maximum index of characters on the go.
def partitionLabels(S):
last = {char: i for i, char in enumerate(S)}
j = anchor = 0
result = []
for i, char in enumerate(S):
j = max(j, last[char])
if i == j:
result.append(i - anchor + 1)
anchor = i + 1
return resultimport java.util.ArrayList;
import java.util.List;
class PartitionLabels {
public List<Integer> partitionLabels(String s) {
int[] lastIndexes = new int[26];
for (int i = 0; i < s.length(); i++) {
lastIndexes[s.charAt(i) - 'a'] = i;
}
List<Integer> partitionSizes = new ArrayList<>();
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, lastIndexes[s.charAt(i) - 'a']);
if (i == end) {
partitionSizes.add(end - start + 1);
start = i + 1;
}
}
return partitionSizes;
}
}#include <iostream>
#include <vector>
#include <string>
std::vector<int> partitionLabels(std::string s) {
std::vector<int> last(26, 0);
// Record last occurrence of each character
for (int i = 0; i < s.size(); ++i) {
last[s[i] - 'a'] = i;
}
std::vector<int> result;
int start = 0, end = 0;
for (int i = 0; i < s.size(); ++i) {
end = std::max(end, last[s[i] - 'a']);
if (i == end) {
result.push_back(end - start + 1);
start = i + 1;
}
}
return result;
}var partitionLabels = function(s) {
let last = {};
for (let i = 0; i < s.length; i++) {
last[s[i]] = i;
}
let result = [];
let start = 0;
let max_index = 0;
for (let i = 0; i < s.length; i++) {
max_index = Math.max(max_index, last[s[i]]);
if (i === max_index) {
result.push(max_index - start + 1);
start = i + 1;
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int* partitionLabels(char* s, int* returnSize) {
int map[26] = {0};
int len = strlen(s);
for (int i = 0; i < len; i++) {
map[s[i] - 'a'] = i;
}
int start = 0, max_index = 0;
int* result = (int*)malloc(len * sizeof(int));
int resultIndex = 0;
for (int i = 0; i < len; i++) {
if (map[s[i] - 'a'] > max_index) {
max_index = map[s[i] - 'a'];
}
if (i == max_index) {
result[resultIndex++] = max_index - start + 1;
start = i + 1;
}
}
*returnSize = resultIndex;
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> PartitionLabels(string s) {
int[] lastIndexes = new int[26];
for (int i = 0; i < s.Length; i++) {
lastIndexes[s[i] - 'a'] = i;
}
IList<int> partitionSizes = new List<int>();
int start = 0, end = 0;
for (int i = 0; i < s.Length; i++) {
end = Math.Max(end, lastIndexes[s[i] - 'a']);
if (i == end) {
partitionSizes.Add(end - start + 1);
start = i + 1;
}
}
return partitionSizes;
}
}In Python, this approach establishes lookup dictionary for last-found indices, followed by a wrap extending these as necessary to determine segment cut points, leading to length registration. The segments are computed end-to-end.
Time Complexity: O(n), courtesy of sequential pass subroutine calls.
Space Complexity: O(1) factoring limited constant space irrelevance in relation to string extent.
Approach 3: Greedy
We first use an array or hash table last to record the last occurrence of each letter in the string s.
Next, we use a greedy approach to partition the string into as many segments as possible.
Traverse the string s from left to right, while maintaining the start index j and end index i of the current segment, both initially set to 0.
For each letter c visited, get the last occurrence position last[c]. Since the end index of the current segment must not be less than last[c], let mx = max(mx, last[c]).
When visiting the index mx, it means the current segment ends. The index range of the current segment is [j,.. i], and the length is i - j + 1. We add this length to the result array. Then set j = i + 1 and continue to find the next segment.
Repeat the above process until the string traversal is complete to get the lengths of all segments.
Time complexity is O(n), and space complexity is O(|\Sigma|). Where n is the length of the string s, and |\Sigma| is the size of the character set. In this problem, |\Sigma| = 26.
function partitionLabels(s: string): number[] {
const last: number[] = Array(26).fill(0);
const idx = (c: string) => c.charCodeAt(0) - 'a'.charCodeAt(0);
const n = s.length;
for (let i = 0; i < n; ++i) {
last[idx(s[i])] = i;
}
const ans: number[] = [];
for (let i = 0, j = 0, mx = 0; i < n; ++i) {
mx = Math.max(mx, last[idx(s[i])]);
if (mx === i) {
ans.push(i - j + 1);
j = i + 1;
}
}
return ans;
}func partitionLabels(s string) (ans []int) {
last := [26]int{}
for i, c := range s {
last[c-'a'] = i
}
var mx, j int
for i, c := range s {
mx = max(mx, last[c-'a'])
if mx == i {
ans = append(ans, i-j+1)
j = i + 1
}
}
return
}impl Solution {
pub fn partition_labels(s: String) -> Vec<i32> {
let n = s.len();
let bytes = s.as_bytes();
let mut last = [0; 26];
for i in 0..n {
last[(bytes[i] - b'a') as usize] = i;
}
let mut ans = vec![];
let mut j = 0;
let mut mx = 0;
for i in 0..n {
mx = mx.max(last[(bytes[i] - b'a') as usize]);
if mx == i {
ans.push((i - j + 1) as i32);
j = i + 1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Method with Last Occurrence | Time Complexity: O(n), where n is the length of the string. |
| Two-Pass Trick | Time Complexity: O(n), courtesy of sequential pass subroutine calls. |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Last Occurrence | O(n) | O(1) | Best general solution. Easy to reason about interval boundaries and commonly expected in interviews. |
| Two-Pass Frequency Trick | O(n) | O(1) | Useful when reasoning about remaining character counts rather than last indices. |
Frequently asked questions
Is Partition Labels easy or hard?
Partition Labels is rated Medium on LeetCode but often feels easier once the greedy insight is discovered. The challenge is recognizing that partitions depend on the last occurrence of characters rather than trying all possible splits.
Partition Labels Python/Java solution
Python and Java implementations follow the same greedy strategy. Store the last index of each character, iterate through the string, and expand the current partition boundary using the stored indices. Once the scan index reaches the boundary, record the partition size.
How to solve Partition Labels in O(n)?
First compute the last index of every character in the string. Then iterate through the string while tracking the farthest last occurrence among characters seen so far. When the current index equals that boundary, finalize a partition and start a new one. Each character is processed a constant number of times, giving O(n) time.
What is the best approach for Partition Labels?
The greedy last-occurrence method is the best approach. Record the last index of each character, then scan the string while expanding the current partition to the farthest last occurrence seen so far. When the current index reaches that boundary, close the partition. This runs in O(n) time and O(1) space.
Is Partition Labels asked at Google/Amazon/Meta?
Partition Labels appears in interview preparation sets and has been reported in coding rounds at companies like Amazon and Meta. It tests greedy reasoning, interval boundaries, and efficient string traversal, which are common patterns in technical interviews.
What data structure is used in Partition Labels?
Most solutions use a hash table or fixed-size array to store the last occurrence index of each character. This structure allows constant-time lookup while scanning the string to determine partition boundaries.
What is the time complexity of Partition Labels?
The optimal solution runs in O(n) time where n is the length of the string. One pass records the last occurrence of each character and another pass determines partition boundaries. Space complexity is O(1) because the algorithm only stores indices for the 26 lowercase letters.