Vultr DocsLatest Content

Partition Labels

Updated on 20 June, 2025
Partition Labels header image

Problem Statement

In this problem, you are provided with a string s, and the objective is to partition this string into the maximum number of parts such that no letter appears in more than one part. The partitions are required to be in such a way that when concatenated in sequence, they reform the original string s. Each partition's individual size is then returned as part of a list. The task demands a careful assessment of character frequencies and their respective last occurrences in the string to determine the valid cut points which define each partition.

Examples

Example 1

Input:

s = "ababcbacadefegdehijhklij"

Output:

[9,7,8]

Explanation:

The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.

Example 2

Input:

s = "eccbbbbdec"

Output:

[10]

Constraints

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

Approach and Intuition

To solve this problem efficiently, follow the steps below:

  1. Identify Character Boundaries:

    • First, we need to determine the last position of each character in the string s. This can be done by traversing the string and updating the last occurrence index of each character.

  2. Determine Cut Points for Partitions:

    • Begin a new partition every time you encounter a character where all characters in the current partition have had their last occurrences.
    • Use two pointers approach where one pointer iterates over the string and the other marks the end of the current partition. As you iterate, update the end of the partition to the farthest last occurrence of any character found within the current partition.

  3. Collect Partition Lengths:

    • When the current pointer (i) reaches the end of the partition (end), it indicates that all characters in the current partition have been accounted for within this segment. At this point, record the length of the partition.
    • Reset the starting point of the next partition to just after the current end.

For example, for the string s = "ababcbacadefegdehijhklij", follow the steps:

  • As you iterate, update the end boundary when encountering 'a', 'b', 'c', etc. Based on the maximum positions of these characters, determine where the partition ends.
  • Once the partition point (as dictated by the position of end) is reached, that segment is marked as a partition. Then continue to the next segment.

This method ensures each partition contains unique characters without any overlaps between them. This strategy follows from understanding the nature of partitions in which once a character is repeated within a segment, no subsequent partition can have this character without breaking the original requirements. Keep in mind that this problem's constraint (character restricted to lowercase English letters) can be utilized to maintain efficient space complexity using arrays or hash maps for tracking last occurrences.

Solutions

  • Java
  • Python
java 
class Solution {
    public List<Integer> labelPartitions(String inputStr) {
        int[] lastIndex = new int[26];
        for (int i = 0; i < inputStr.length(); ++i)
            lastIndex[inputStr.charAt(i) - 'a'] = i;
        
        int maxIndex = 0, partitionStart = 0;
        List<Integer> result = new ArrayList();
        for (int i = 0; i < inputStr.length(); ++i) {
            maxIndex = Math.max(maxIndex, lastIndex[inputStr.charAt(i) - 'a']);
            if (i == maxIndex) {
                result.add(i - partitionStart + 1);
                partitionStart = i + 1;
            }
        }
        return result;
    }
}

Solution Summary for "Partition Labels" in Java:

The Java class named Solution provides a method called labelPartitions to handle the partitioning of labels based on the provided string inputStr. This method identifies and returns the sizes of the largest substrings (or segments) within the input string such that each character appears only within that segment.

Follow this step-by-step breakdown of the solution:

  1. Initialize a 26-element integer array lastIndex to store the last occurrence position of each letter in the English alphabet. The index 0 represents 'a', 1 represents 'b', and so on up to 25 for 'z'.

  2. Iterate through each character of the input string. For each character, update its last occurrence in the lastIndex array.

  3. Define two integers: maxIndex and partitionStart, both set to 0 at the beginning. maxIndex tracks the farthest position in the string that must be included in the current partition due to character reappearance. partitionStart indicates the starting point of the current partition.

  4. Iterate again through the string. For each character:

    • Update maxIndex to be the maximum value between its current value and the last occurrence of the current character.
    • Check if the current position i matches maxIndex. If true, calculate the size of the current partition by subtracting partitionStart from i, add 1 (to account for zero-based index), append this size to the result list, and reset partitionStart to the next position i + 1.
  • After completing the iterations, the method returns the list result containing the sizes of all the identified partitions.

This approach ensures that each partition is maximal, meaning no character starts in one and ends in another partition, leveraging the recorded last occurrences efficiently with a linear scan through the string.

python 
class Solution(object):
    def splitString(self, input_string):
        last_occurrence = {char: idx for idx, char in enumerate(input_string)}
        max_index = start = 0
        result = []
        for index, char in enumerate(input_string):
            max_index = max(max_index, last_occurrence[char])
            if index == max_index:
                result.append(index - start + 1)
                start = index + 1
        
        return result

For the problem 'Partition Labels', the provided Python solution involves determining the sizes of the partitions in a given string where each letter only appears in one partition. Observe the solution strategy outlined below:

  • Create a dictionary last_occurrence to map each character to its last occurrence index in input_string.
  • Initialize max_index to keep track of the furthest index any character in the current partition last appears.
  • Use start to remember the index at the beginning of each new partition.
  • Iterate through input_string using a for loop to examine each character.
  • Update max_index for each character you come across, using the dictionary.
  • Check if the current index equals max_index. If true, you've found a partition boundary:
    • Append the size of the current partition to result list.
    • Update start to the next character's index to begin a new partition.
  • Return the list result that contains the sizes of these partitions.

This approach ensures that each character of the input string is accounted for in exactly one partition, and these partitions are as large as possible while meeting the requirement. The efficiency of this solution comes from the linear scans made to both build the last occurrences dictionary and determine the partitions—a process which is effective and easy to understand.

Comments

No comments yet.