Partition Labels Problem

Problem

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.

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

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.

Main condition is - “Characters do not appear beyond their partition.”. Let’s understand with an example, visually:

We skip over the character a until its influence ends - See first partition in orange color
Next we skip over the character b until its influence ends - See first partition in blue color
Now we skip over the character c until its influence ends - See first partition in green color
As you can see, we have one of the partitions up to this point where similar characters are present.

Similarly, we will do the same for the others as well. Finally, return the length of each partition as a list, e.g., [9, 7, 8].

partition-labels-viz1.excalidraw

Example 2:

Input: s = "eccbbbbdec"
Output: [10]

Solution

Method 1 - Track Last Indices of All Chars and See if We Can Break

Here is the algorithm:

Fundamental idea: Each instance of a character should be contained in a single partition.
Start with the first character and determine the position where we can complete the partition.
The earliest point to finish the partition is at the last occurrence of the initial character.
If another character appears between the start and the last occurrence of the first character:
- Extend the length of the partition to include the new character’s last occurrence.
- Not extending the partition would place the new character in two different partitions, violating the problem’s constraints.
Once all characters between the start of the partition and the farthest last occurrences of any character in the segment have been covered, close the partition and begin a new one.

Code

Java

public class Solution {
    public List<Integer> partitionLabels(String s) {
        Map<Character, Integer> map = new HashMap<>();
        // Recording the last occurrence of each character
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            map.put(ch, i);
        }
        
        List<Integer> res = new ArrayList<>();
        int prev = -1;
        int max = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            max = Math.max(max, map.get(ch));
            if (max == i) {
                // it's partition time
                res.add(max - prev);
                prev = max;
            }
        }
        return res;
    }
}

Python

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last: dict = {c: i for i, c in enumerate(s)}
        
        res: List[int] = []
        max_last: int = 0
        prev: int = -1
        
        for i, c in enumerate(s):
            max_last = max(max_last, last[c])
            if i == max_last:
                res.append(i - prev)
                prev = i
        
        return res

Complexity

⏰ Time complexity: O(n), as we traverse each character twice.
🧺 Space complexity: O(1). We use a fixed number of elements (26 for each distinct character). Additional memory is needed only to store the result.

Problem#

Examples#

Solution#

Method 1 - Track Last Indices of All Chars and See if We Can Break#

Code#

Java#

Python#

Complexity#