Partition Labels

Master this topic with zero to advance depth.

Partition Labels

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.

Return a list of integers representing the size of these parts.

Visual Representation

s = "ababcbacadefegdehijhklij"

Letter 'a' appears at indices [0, 2, 6, 8]
If we take 'a', we MUST take everything up to index 8.
Inside [0, 8], we have 'b' (ends at 5), 'c' (ends at 7).
Max end index for characters in [0, 8] is index 8.
Partition 1: "ababcbaca" (Size 9)

Medium

Examples

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
The partition is "ababcbaca", "defegde", "hijhklij".

Approach 1

Level I: Dynamic Search

Intuition

For every partition starting at i, we find the last occurrence of s[i]. This is our initial end. Then, for every character between i and end, we update end if that character's last occurrence is even further.

Thought Process

Iterate i from 0 to $N-1$ .
Start a new partition: start = i, end = lastOccurrence(s[i]).
Loop j from i to end:
- end = max(end, lastOccurrence(s[j])).
When j reaches end, the partition is complete. Add end - start + 1 to result.
Move i to end + 1.

Pattern: Window Expansion

⏱ O(N^2) - If we call `lastIndexOf` inside the loop for each character.💾 O(1) - Just pointers.

Detailed Dry Run

s = "abaccb"

i=0 ('a'), end=2 ('a' at index 2). Partition: [0, 2]
Check inner: j=1 ('b'), last 'b' is 5. Update end=5.
Check inner: j=3 ('c'), last 'c' is 4. end stays 5.
j reaches 5. Partition size = 5-0+1 = 6.

java

import java.util.*;

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

Approach 2

Level II: Merge Intervals

Intuition

Treat each character as an interval from its first occurrence to its last occurrence. Any overlapping intervals MUST be merged into a single partition. This reduces the problem to a standard interval merging task.

Thought Process

Find first and last occurrence for each character 'a'-'z'.
Create a list of intervals [first, last] for characters that appear in the string.
Sort intervals by start time.
Merge overlapping intervals.
The size of each merged interval is a partition length.

Pattern: Interval Merging

⏱ O(N + A log A) where A is alphabet size (26). Effectively O(N).💾 O(A) - Storage for 26 intervals.

Detailed Dry Run

s = "abaccb" Intervals: a[0,2], b[1,5], c[3,4]

Sorted: [0,2], [1,5], [3,4]
Merge [0,2] and [1,5] -> [0,5] (overlaps)
Merge [0,5] and [3,4] -> [0,5] (overlaps) Result: [6]

java

import java.util.*;

public class Solution {
    public List<Integer> partitionLabels(String s) {
        int[][] intervals = new int[26][2];
        for(int[] sub : intervals) Arrays.fill(sub, -1);
        for(int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';
            if(intervals[c][0] == -1) intervals[c][0] = i;
            intervals[c][1] = i;
        }
        List<int[]> list = new ArrayList<>();
        for(int[] interval : intervals) if(interval[0] != -1) list.add(interval);
        list.sort((a, b) -> a[0] - b[0]);
        List<Integer> res = new ArrayList<>();
        if(list.isEmpty()) return res;
        int start = list.get(0)[0], end = list.get(0)[1];
        for(int i = 1; i < list.size(); i++) {
            if(list.get(i)[0] <= end) end = Math.max(end, list.get(i)[1]);
            else {
                res.add(end - start + 1);
                start = list.get(i)[0]; end = list.get(i)[1];
            }
        }
        res.add(end - start + 1);
        return res;
    }
}

Approach 3

Level III: Optimal Greedy (One-Pass)

Intuition

As we scan the string, we keep track of the maximum last index seen so far for characters in the current partition. When our current index i catches up to this last index, we've found a valid partition.

Thought Process

Store the lastIndex for every character in a map/array.
Maintain start and end pointers.
Iterate i from 0 to $N-1$ $N - 1$ :
- end = max(end, lastIndex[s[i]]).
- If i == end:
  - Found partition! Size = i - start + 1.
  - Update start = i + 1.

Pattern: Greedy Boundary Tracking

⏱ O(N) - One pass to build the map, one pass to partition.💾 O(1) - Map size is constant (26 characters).

Detailed Dry Run

s = "ababcbaca..."

i	char	lastIndex[char]	end	Action
0	a	8	8	-
1	b	5	8	-
...	...	...	8	-
8	a	8	8	i == end! Size = 8-0+1 = 9. start = 9.

java

import java.util.*;

public 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(i - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
}

← Previous QuestionGas Station

Next Question →Minimum Number of Arrows to Burst Balloons

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.