Code Implementation

class Solution:
    def partitionLabels(self, s: str) -> list[int]:
        last = {ch: i for i, ch in enumerate(s)}
        partitions = []
        start = end = 0
        for i, ch in enumerate(s):
            end = max(end, last[ch])
            if i == end:
                partitions.append(end - start + 1)
                start = i + 1
        return partitions
      

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> res;
        int start = 0, end = 0;
        for (int i = 0; i < s.size(); ++i) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) {
                res.push_back(end - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
};
      

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

var partitionLabels = function(s) {
    const last = {};
    for (let i = 0; i < s.length; ++i)
        last[s[i]] = i;
    const res = [];
    let start = 0, end = 0;
    for (let i = 0; i < s.length; ++i) {
        end = Math.max(end, last[s[i]]);
        if (i === end) {
            res.push(end - start + 1);
            start = i + 1;
        }
    }
    return res;
};
      

Problem Description

Given a string s, you are to partition it into as many parts as possible so that each letter appears in at most one part. After partitioning, return a list of integers representing the size of these parts.

Key constraints:

• Each character can only appear in one partition.
• You must partition so that the number of parts is maximized.
• There is always at least one valid solution.

Thought Process

At first glance, one might consider checking all possible partitions and verifying for each if the condition is met, but this would be extremely inefficient. We want to maximize the number of partitions, but we must ensure that no character appears in more than one partition.

The key insight is: for every character, all its occurrences must be contained within a single partition. So, if we know the last position of each character, we can determine the minimum range that must be included for each partition. When iterating through the string, we can expand the current partition to cover the last occurrence of each character we see. When our current index matches the farthest last occurrence seen so far, we know we can safely cut the partition here.

Solution Approach

To solve the problem efficiently, we follow these steps:

1. Record Last Occurrences:
   • First, iterate through the string and map each character to its last index in the string. This can be done using a hash map (dictionary) or an array for lowercase letters.
2. Iterate and Expand Partitions:
   • Start iterating through the string again, maintaining two pointers: start (start of current partition) and end (end of current partition).
   • For each character at index i, update end to be the maximum of the current end and the last occurrence of the character at i.
3. Cut When Possible:
   • When the current index i reaches end, it means all characters in the current partition do not appear later. Record the size (end - start + 1) and start a new partition from i+1.
4. Repeat:
   • Continue this process until you reach the end of the string.

Example Walkthrough

Let's use the example s = "ababcbacadefegdehijhklij":

1. Map last occurrences:
   • a: 8, b: 5, c: 7, d: 14, e: 15, f: 11, g: 13, h: 19, i: 22, j: 23, k: 20, l: 21
2. Start partitioning:
   • Start at index 0, end at 8 (last 'a'). As you move from 0 to 8, you update end to max of current end and last index of current char. At index 8, end==8, so partition size is 9.
   • Start at 9, end at 15 (last 'e'). As you move, update end as needed. At index 15, end==15, so partition size is 7.
   • Start at 16, end at 23 (last 'j'). At index 23, end==23, so partition size is 8.
3. Result:
   • The partitions are [9, 7, 8], matching the expected output.

Time and Space Complexity

Brute-force approach: Would involve checking all possible partitions and verifying each for the unique occurrence condition, which is exponential time (very inefficient and impractical).

Optimized approach:

• Time Complexity: O(N), where N is the length of the string. We make two passes: one to record last occurrences and one to partition.
• Space Complexity: O(1) if the alphabet is fixed (e.g., lowercase English letters), since the hash map/array size does not grow with input size. Otherwise, O(K) where K is the number of unique characters.

Summary

The Partition Labels problem is elegantly solved by tracking the last occurrence of each character and expanding partitions greedily to ensure no character crosses partition boundaries. This allows for a linear-time solution that is both efficient and easy to understand. The approach leverages simple data structures and a two-pass strategy, making it a classic example of how pre-processing and greedy methods can simplify what initially seems to be a complex partitioning task.