Partition Labels Greedy DSA Solution - Study Chapter | QuizMaker

Partition Labels explained with cut validation brute force, optimized last occurrence greedy, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 13: Greedy Algorithms

Learning Outcome

After this lesson, you should be able to use last occurrence positions as dynamic boundaries for greedy cuts.

Problem Statement

Given a string, partition it into as many parts as possible so each character appears in at most one part. Return the sizes of the parts.

Input	Output	Why
`s = "ababcbacadefegdehijhklij"`	`[9,7,8]`	The first partition must end at index 8 because a, b, and c all appear within that boundary.

Brute Force Approach

Try every cut and validate whether characters appear across multiple parts. This is slow.

Optimized Approach

Precompute the last index of every character. While scanning, extend the current partition end to the farthest last occurrence seen so far.

Exact Pseudocode

last[ch] = final index of ch
start = 0
end = 0
for i from 0 to length(s) - 1:
  end = max(end, last[s[i]])
  if i == end:
    answer.add(end - start + 1)
    start = i + 1
return answer

Reference Code

class Solution:
    def partitionLabels(self, s):
        last = {ch: i for i, ch in enumerate(s)}
        answer = []
        start = 0
        end = 0

        for i, ch in enumerate(s):
            end = max(end, last[ch])
            if i == end:
                answer.append(end - start + 1)
                start = i + 1

        return answer

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> last(26, 0);
        for (int i = 0; i < s.size(); i++) {
            last[s[i] - 'a'] = i;
        }

        vector<int> answer;
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.size(); i++) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) {
                answer.push_back(end - start + 1);
                start = i + 1;
            }
        }
        return answer;
    }
};

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> answer = new ArrayList<>();
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                answer.add(end - start + 1);
                start = i + 1;
            }
        }
        return answer;
    }
}

Sample Dry Run

Step	State	Result
Precompute last	a ends at 8, b at 5, c at 7	Boundaries are known
Scan first partition	end expands to 8	Cannot cut before 8
i = 8	i equals end	Add size 9
Continue	Next partitions close at 15 and 23	sizes [9,7,8]

Complexity

Measure	Value	Reason
Time	O(n)	The string is scanned twice.
Space	O(1)	For lowercase English letters, last positions use fixed space.

Edge Cases

A string with one repeated character becomes one partition.
Each character must appear in at most one output part.
Use the correct character range for the input.

Interview Checklist

Precompute last occurrence for every character.
Extend end while scanning the current partition.
Cut only when i reaches end.

FAQs

Why can we cut when i equals end?

Every character seen in the current partition has its last occurrence at or before this index.

Why not cut at first repeat?

Other characters inside the segment may appear later, so the boundary must track all last occurrences.

What is the core pattern?

Last occurrence boundary greedy.