Medium — Hash Table | Two Pointers | String | Greedy

The Problem

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

Approach

First, record the last occurrence index of each character. Then iterate through the string, keeping track of the furthest last index needed to include all characters seen so far. When the current index reaches this furthest point, we can create a partition.

Time: O(n) · Space: O(1)

Code

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_index = {}

        for i, char in enumerate(s):
            last_index[char] = i

        result = []
        start, end = 0, 0

        for i, char in enumerate(s):
            end = max(end, last_index[char])

            if i == end:
                result.append(end - start + 1)
                start = end + 1

        return result

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment