Is Partition Labels easy or hard?

Partition Labels is rated Medium on LeetCode but often feels easier once the greedy insight is discovered. The challenge is recognizing that partitions depend on the last occurrence of characters rather than trying all possible splits.

Partition Labels Python/Java solution

Python and Java implementations follow the same greedy strategy. Store the last index of each character, iterate through the string, and expand the current partition boundary using the stored indices. Once the scan index reaches the boundary, record the partition size.

How to solve Partition Labels in O(n)?

First compute the last index of every character in the string. Then iterate through the string while tracking the farthest last occurrence among characters seen so far. When the current index equals that boundary, finalize a partition and start a new one. Each character is processed a constant number of times, giving O(n) time.

What is the best approach for Partition Labels?

The greedy last-occurrence method is the best approach. Record the last index of each character, then scan the string while expanding the current partition to the farthest last occurrence seen so far. When the current index reaches that boundary, close the partition. This runs in O(n) time and O(1) space.

Is Partition Labels asked at Google/Amazon/Meta?

Partition Labels appears in interview preparation sets and has been reported in coding rounds at companies like Amazon and Meta. It tests greedy reasoning, interval boundaries, and efficient string traversal, which are common patterns in technical interviews.

What data structure is used in Partition Labels?

Most solutions use a hash table or fixed-size array to store the last occurrence index of each character. This structure allows constant-time lookup while scanning the string to determine partition boundaries.

What is the time complexity of Partition Labels?

The optimal solution runs in O(n) time where n is the length of the string. One pass records the last occurrence of each character and another pass determines partition boundaries. Space complexity is O(1) because the algorithm only stores indices for the 26 lowercase letters.

Description Hints 1 Solution Video 14:29

763. Partition Labels

Medium81.8% acceptance9 companies

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.

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.

Asked at 9 companies

Barclays Inmobi Microsoft Amazon

Infosys Bloomberg LinkedIn

Google Meta

Topics

Hints open one at a time

Hint 1

Try to greedily choose the smallest partition that includes the first letter. If you have something like "abaccbdeffed", then you might need to add b. You can use an map like "last['b'] = 5" to help you expand the width of your partition.

14:29

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution