Partition Labels

Problem Description

You are given a string s. We want to partition the string into as many parts as possible so that each character 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.

Examples

Constraints

• 1 ≤ s.length ≤ 500
• s consists of lowercase English letters.

Track the Last Occurrence of Each Character

A partition boundary can only be placed at index i if every character seen so far in the current part does not appear anywhere after i.

To implement this:

1. Make a first pass to record the last index occurrence of each character in s.
2. Keep a start pointer (the beginning of the current part) and an end pointer (the farthest last-occurrence index of any character seen in the current part).
3. Traverse the string:
   • For each character s[i], update end = max(end, last_occurrence[s[i]]).
   • If we reach i == end, we have found a valid partition boundary. Record the size of the current part: i - start + 1.
   • Set start = i + 1 for the next part.

Solution: Greedy Boundary Tracking

import java.util.*;

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        int n = s.length();
        for (int i = 0; i < n; i++) {
            last[s.charAt(i) - 'a'] = i;
        }

        List<Integer> result = new ArrayList<>();
        int start = 0, end = 0;

        for (int i = 0; i < n; i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                result.add(end - start + 1);
                start = i + 1;
            }
        }

        return result;
    }
}

class Solution:
    def partitionLabels(self, s: str) -> list[int]:
        # Record the last occurrence of each character
        last = {char: i for i, char in enumerate(s)}
        
        result = []
        start = 0
        end = 0
        
        for i, char in enumerate(s):
            end = max(end, last[char])
            if i == end:
                result.append(end - start + 1)
                start = i + 1
                
        return result

#include <vector>
#include <string>
#include <algorithm>

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

        std::vector<int> result;
        int start = 0, end = 0;

        for (int i = 0; i < n; i++) {
            end = std::max(end, last[s[i] - 'a']);
            if (i == end) {
                result.push_back(end - start + 1);
                start = i + 1;
            }
        }

        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the length of the string s. We make two passes over the string.
• Space Complexity: O(1) auxiliary space (the frequency table has a fixed size of 26).

← All Problems