Partition Labels
Partition Labels is a medium intervals problem solved with the basics pattern.
The best approach, optimal (last-index table + greedy cut), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (rescan for last occurrences) up.
Problem
You are given a string s of lowercase letters. Cut it into as many contiguous parts as possible such that each letter appears in at most one part.
Return a list with the length of every part, from left to right. Concatenating the parts in order must give back s.
Examples
Example 1
- Input
s = "abacdcefge"- Output
[3, 3, 4]- Why
- Parts "aba", "cdc" and "efge": every letter lives in exactly one part, and no part can be split further.
Example 2
- Input
s = "xyz"- Output
[1, 1, 1]- Why
- All letters are different, so each one can be its own part.
Example 3
- Input
s = "mnopm"- Output
[5]- Why
- 'm' appears at both ends, so the whole string must stay together.
Constraints
1 <= s.length <= 500sconsists only of lowercase English letters
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (rescan for last occurrences) | O(n²) | O(1) |
| Optimal (last-index table + greedy cut) | O(n) | O(1) |
1Brute force (rescan for last occurrences)
O(n²)Each of the n positions may scan the string from the right to find its last occurrence.O(1)Only a few indices besides the output.Start a part at index start. Keep an end pointer; for every index i inside the part, scan the rest of the string to find the last occurrence of s[i] and push end out to it. When i passes end, the part is closed and the next one starts.
- start = 0.
- While start < n: end = start; for i from start while i <= end: find the last index of s[i] by scanning from the right, end = max(end, that index).
- Record end - start + 1 and set start = end + 1.
- Return the recorded sizes.
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> sizes = new ArrayList<>();
int n = s.length(), start = 0;
while (start < n) {
int end = start;
for (int i = start; i <= end; i++) {
int last = n - 1;
while (s.charAt(last) != s.charAt(i)) last--;
end = Math.max(end, last);
}
sizes.add(end - start + 1);
start = end + 1;
}
return sizes;
}
}class Solution:
def partitionLabels(self, s: str) -> List[int]:
sizes = []
n, start = len(s), 0
while start < n:
end = start
i = start
while i <= end:
last = n - 1
while s[last] != s[i]:
last -= 1
end = max(end, last)
i += 1
sizes.append(end - start + 1)
start = end + 1
return sizesclass Solution {
public:
vector<int> partitionLabels(string s) {
vector<int> sizes;
int n = s.size(), start = 0;
while (start < n) {
int end = start;
for (int i = start; i <= end; i++) {
int last = n - 1;
while (s[last] != s[i]) last--;
end = max(end, last);
}
sizes.push_back(end - start + 1);
start = end + 1;
}
return sizes;
}
};function partitionLabels(s) {
const sizes = [];
const n = s.length;
let start = 0;
while (start < n) {
let end = start;
for (let i = start; i <= end; i++) {
let last = n - 1;
while (s[last] !== s[i]) last--;
end = Math.max(end, last);
}
sizes.push(end - start + 1);
start = end + 1;
}
return sizes;
}2Optimal (last-index table + greedy cut)
O(n)Two linear passes over the string.O(1)A fixed array of 26 indices (output not counted).Record the last index of each of the 26 letters in one pass. Then scan again, stretching the current part's end to last[s[i]] for every letter seen. When i == end, every letter of the part has had its final appearance, so this is the earliest legal cut; cutting as early as possible yields the most parts.
- last[c] = the largest index of letter c.
- start = 0, end = 0.
- For i in 0..n-1: end = max(end, last[s[i]]); if i == end, record i - start + 1 and set start = i + 1.
- Return the recorded sizes.
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> sizes = 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) {
sizes.add(i - start + 1);
start = i + 1;
}
}
return sizes;
}
}class Solution:
def partitionLabels(self, s: str) -> List[int]:
last = {c: i for i, c in enumerate(s)}
sizes = []
start = end = 0
for i, c in enumerate(s):
end = max(end, last[c])
if i == end:
sizes.append(i - start + 1)
start = i + 1
return sizesclass Solution {
public:
vector<int> partitionLabels(string s) {
int last[26] = {0};
for (int i = 0; i < (int)s.size(); i++) last[s[i] - 'a'] = i;
vector<int> sizes;
int start = 0, end = 0;
for (int i = 0; i < (int)s.size(); i++) {
end = max(end, last[s[i] - 'a']);
if (i == end) {
sizes.push_back(i - start + 1);
start = i + 1;
}
}
return sizes;
}
};function partitionLabels(s) {
const last = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) last[s.charCodeAt(i) - 97] = i;
const sizes = [];
let start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
end = Math.max(end, last[s.charCodeAt(i) - 97]);
if (i === end) {
sizes.push(i - start + 1);
start = i + 1;
}
}
return sizes;
}Edge cases to test
- A single character
- All characters the same
- All characters distinct (every part has length 1)
- The first and last characters are equal (one part)
Hints
Hint 1
Once a letter appears in a part, the part must reach at least that letter's last occurrence.
Hint 2
Precompute the last index of every letter.
Hint 3
Walk left to right, extending the current part's end to the last index of each letter you meet; when your position reaches that end, close the part.
FAQ
What is the best time complexity for Partition Labels?
Optimal (last-index table + greedy cut) runs in O(n) time and O(1) extra space. Two linear passes over the string.
Which pattern does Partition Labels use?
It is a intervals problem that uses the basics pattern. Other problems with the same pattern: Detect overlap unsorted, Detect overlap sorted intervals, Interval List Intersections.
Is there a brute force solution for Partition Labels?
Yes. Brute force (rescan for last occurrences) takes O(n²) time and O(1) space. Start a part at index start.
Which edge cases should I test for Partition Labels?
A single character; All characters the same; All characters distinct (every part has length 1); The first and last characters are equal (one part).