Log inSign up
mediumLeetCodeNot Started

Partition Labels

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

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 · Example 1: Standard Partitioning:

Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]
Explanation: The partition is "ababcbaca", "defegde", "hijhklij".\nEach letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is invalid because it has fewer parts.

Example 2 · Example 2: All Same Character:

Input: s = "eccbbbbdec"
Output: [10]
Explanation: e and c appear at the beginning and the end, forcing the entire string to be 1 partition of size 10.

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why greedily cutting at the earliest valid boundary maximizes partition count.
  • Implement the two-pointer last occurrence boundary algorithm.
  • Write clean, idiomatic solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Partition string into maximum number of disjoint segments.
  • Characters must be confined to single contiguous partitions.
  • Letter frequency / last appearance boundary constraint.

Algorithmic Decision Tree:

  • Precompute last occurrence map.
  • Extend partition boundary end = max(end, last[s[i]]).
  • Cut when i == end.

Connected Patterns:

Jump Game IIMerge IntervalsValid Palindrome II

1. Recursive Partitioning Verification

Intuition

Recursively attempt every valid cut point where characters in the prefix do not occur in the remainder of the string.

Algorithm

  1. Step 1: Define recursive solve(idx).
  2. Step 2: If idx == s.length(), return empty partition list.
  3. Step 3: Scan forward to find the smallest j >= idx such that characters in s[idx..j] do not appear in s[j+1..end].
  4. Step 4: Append (j - idx + 1) to result and recurse on solve(j + 1).
  5. Step 5: Return partitions.

Enumerate Cut Boundaries & Validate Disjoint Sets

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Characters 'a' and 'b' cross the boundary into the suffix
Visual state
Values and pointers at this exact step
pointers
S
a
b
a
b
c
b
a
c
a
0
1
2
3
↑ cut
4
5
6
7
8
Variables at this step
cutCandidate
3
valid
false
Check / comparison
Test candidate cut at index 3: prefix s[0..3] = "abab"
Decision / next transition
Invalid cut: 'a' and 'b' appear again at indices 5, 6, 8.
Why this step matters

Characters a and b cross the boundary into the suffix. The cut must be extended.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5
6using namespace std;
7
8class Solution {
9public:
10 vector<int> partitionLabels(string s) {
11 vector<int> ans;
12 int n = s.length();
13 int i = 0;
14
15 while (i < n) {
16 unordered_set<char> seen;
17 int j = i;
18 seen.insert(s[i]);
19
20 for (int k = i; k <= j; ++k) {
21 seen.insert(s[k]);
22 // Extend j to the last occurrence of any seen character
23 for (int m = n - 1; m > j; --m) {
24 if (s[m] == s[k]) {
25 j = m;
26 break;
27 }
28 }
29 }
30
31 ans.push_back(j - i + 1);
32 i = j + 1;
33 }
34
35 return ans;
36 }
37};
38
39int main() {
40 Solution sol;
41 string s = "ababcbacadefegdehijhklij";
42 vector<int> res = sol.partitionLabels(s);
43 cout << "Partition Sizes: ";
44 for (int len : res) cout << len << " ";
45 cout << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(2^N)
  • Space complexity: O(N)

2. Character Interval Merging

Intuition

Compute [firstAppearance, lastAppearance] interval for each distinct character. Merge overlapping intervals to get partition sizes.

Algorithm

  1. Step 1: Find first and last occurrence for each character in string s.
  2. Step 2: Collect all intervals [first, last] and sort by start coordinate.
  3. Step 3: Merge overlapping intervals.
  4. Step 4: Output the length of each merged interval (end - start + 1).

Character Interval Merging

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
'b' and 'c' intervals lie completely inside [0, 8], merging into one cluster
Visual state
Values and pointers at this exact step
intervals
a
[0, 8]
↑ group 1
b
[1, 5]
c
[4, 7]
mergedSpan[0, 8]
length9
Variables at this step
mergedSpan
[0, 8]
length
9
Check / comparison
Intervals for 'a': [0,8], 'b': [1,5], 'c': [4,7]
Decision / next transition
Merge [0,8], [1,5], [4,7] into single interval [0, 8].
Why this step matters

b and c intervals lie completely inside [0, 8], merging into one cluster.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 vector<int> partitionLabels(string s) {
11 vector<int> first(26, -1), last(26, -1);
12 for (int i = 0; i < (int)s.size(); ++i) {
13 int c = s[i] - 'a';
14 if (first[c] == -1) first[c] = i;
15 last[c] = i;
16 }
17
18 vector<pair<int, int>> intervals;
19 for (int i = 0; i < 26; ++i) {
20 if (first[i] != -1) intervals.push_back({first[i], last[i]});
21 }
22 sort(intervals.begin(), intervals.end());
23
24 vector<int> ans;
25 int curStart = intervals[0].first;
26 int curEnd = intervals[0].second;
27
28 for (size_t i = 1; i < intervals.size(); ++i) {
29 if (intervals[i].first <= curEnd) {
30 curEnd = max(curEnd, intervals[i].second);
31 } else {
32 ans.push_back(curEnd - curStart + 1);
33 curStart = intervals[i].first;
34 curEnd = intervals[i].second;
35 }
36 }
37 ans.push_back(curEnd - curStart + 1);
38
39 return ans;
40 }
41};
42
43int main() {
44 Solution sol;
45 string s = "ababcbacadefegdehijhklij";
46 vector<int> res = sol.partitionLabels(s);
47 cout << "Partition Sizes (Intervals): ";
48 for (int len : res) cout << len << " ";
49 cout << endl;
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(N + K log K) where K <= 26
  • Space complexity: O(K)

3. Greedy Last Occurrence Boundary Tracking

Intuition

Precompute the last occurrence of each character. In a second pass, maintain the furthest end boundary required by characters seen so far. Commit partition when index equals boundary.

Algorithm

  1. Step 1: Create an array lastIdx of size 26. Store lastIdx[s[i] - a] = i for each character.
  2. Step 2: Initialize start = 0, end = 0, and ans list.
  3. Step 3: Iterate through each character at index i from 0 to s.length() - 1.
  4. Step 4: Update end = max(end, lastIdx[s[i] - a]).
  5. Step 5: If i reaches end, record partition length (end - start + 1), and update start = i + 1.
  6. Step 6: Return ans.

Greedy Expanding Window with Last Occurrences

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Since 'a' appears at index 8, the current partition must extend at least to index 8
Visual state
Values and pointers at this exact step
pointers
S
a
b
a
b
c
b
a
c
a
0
↑ start
1
2
3
4
5
6
7
8
↑ end
Variables at this step
i
0
start
0
end
8
char
a
Check / comparison
i = 0 ('a'): last['a'] = 8
Decision / next transition
Set start = 0, end = max(0, 8) = 8.
Why this step matters

Since a appears at index 8, the current partition must extend at least to index 8.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 vector<int> partitionLabels(string s) {
11 vector<int> lastIdx(26, 0);
12 for (int i = 0; i < (int)s.size(); ++i) {
13 lastIdx[s[i] - 'a'] = i;
14 }
15
16 vector<int> ans;
17 int start = 0, end = 0;
18
19 for (int i = 0; i < (int)s.size(); ++i) {
20 end = max(end, lastIdx[s[i] - 'a']);
21 if (i == end) {
22 ans.push_back(end - start + 1);
23 start = i + 1;
24 }
25 }
26
27 return ans;
28 }
29};
30
31int main() {
32 Solution sol;
33 string s = "ababcbacadefegdehijhklij";
34 vector<int> res = sol.partitionLabels(s);
35 cout << "Partition Sizes (Optimal): ";
36 for (int len : res) cout << len << " ";
37 cout << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Recursive Split VerificationO(2^N)O(N)Recursively try splitting the string at every position and verify that no character appears in multiple segments.Testing all 2^(N-1) partition splits.
2.Better — Interval Creation & MergingO(N + K log K) where K <= 26O(K)Find [first_idx, last_idx] interval for each distinct character. Sort these intervals by start time and merge overlapping intervals. Output merged lengths.Interval creation and sorting.
3.Optimal — Greedy Last Occurrence Boundary TrackingOptimalO(N)O(1) auxiliary (fixed 26 array)Store last occurrence of each char in an array of size 26. In one pass, expand boundary end = max(end, last[s[i]]). When i == end, commit the partition.Two linear scans.
Back to DSA Sheet