Partition Labels

Greedy

20 min

Problem Statement

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. Return a list of integers representing the size of these parts.

Example

Example 1:

Input: s = "ababcbacadefegdehijhklij"

s: "ababcbacadefegdehijhklij"

Output: [9, 7, 8]

Output: [9,7,8]

Solution

The greedy approach is to find the last occurrence of each character. Then, we iterate through the string, keeping track of the maximum last occurrence seen so far. When the current index matches the maximum last occurrence, we know we can make a partition.

Algorithm Steps

First, create a map to store the last occurrence index of each character.
Initialize `size` and `end` to 0, and an empty result list.
Iterate through the string with a pointer `i`.
Update `end` to be the maximum of `end` and the last occurrence of the character `s[i]`.
Increment `size`.
If `i` equals `end`, it means we have reached the end of a partition. Add `size` to the result list and reset `size` to 0.

Partition Labels

Greedy Approach

Input: s = "ababcbacadefegdehijhklij"

Output: []

Progress1 / 1

Ready to start the visualization

String

Partition Size

Partition End

Partition Labels Solution


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