Course4all

Partition Labels

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Greedy.

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

  1. Iterate i from 0 to N−1N-1.
  2. Start a new partition: start = i, end = lastOccurrence(s[i]).
  3. Loop j from i to end:
    • end = max(end, lastOccurrence(s[j])).
  4. When j reaches end, the partition is complete. Add end - start + 1 to result.
  5. 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"
  1. i=0 ('a'), end=2 ('a' at index 2). Partition: [0, 2]
  2. Check inner: j=1 ('b'), last 'b' is 5. Update end=5.
  3. Check inner: j=3 ('c'), last 'c' is 4. end stays 5.
  4. 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

  1. Find first and last occurrence for each character 'a'-'z'.
  2. Create a list of intervals [first, last] for characters that appear in the string.
  3. Sort intervals by start time.
  4. Merge overlapping intervals.
  5. 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]
  1. Sorted: [0,2], [1,5], [3,4]
  2. Merge [0,2] and [1,5] -> [0,5] (overlaps)
  3. 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

  1. Store the lastIndex for every character in a map/array.
  2. Maintain start and end pointers.
  3. Iterate i from 0 to N−1N-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..."
icharlastIndex[char]endAction
0a88-
1b58-
.........8-
8a88i == 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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionGas Station
Next Question →Minimum Number of Arrows to Burst Balloons