LeetCode 763: Partition Labels — Step-by-Step Visual Trace

#python #leetcode #algorithms

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