Partition Labels

mediumPROGreedy & IntervalsAmazon DSA

Given a string s, partition it into as many parts as possible so that each letter appears in at most one part. Return the sizes of these parts as a list of integers, in left-to-right order.

The tests print the returned sizes as space-separated integers.

Example

Input

ababcbacadefegdehijhklij

Output

9 7 8

Reasoning

The input s has 24 lowercase letters at positions $0$ to $23$ . The output lists part lengths from left to right.
Every copy of a letter must land in the same part. The first a is at position $0$ and the last at position $8$ , so the first part covers at least positions $0$ to $8$ . Inside that span, b and c last appear at $5$ and $7$ , so nothing crosses the boundary and the first part is ababcbaca, length $9$ .
The second part starts with d (last copy at $14$ ), and it contains e, whose last copy is at $15$ . Nothing in positions $9$ to $15$ reaches further, giving defegde, length $7$ .
The final part hijhklij covers positions $16$ to $23$ , length $8$ , because j appears again at the very end.
Notice that $9 + 7 + 8 = 24$ . The parts tile the whole string, and each cut is made as early as the letters allow, which is what makes the number of parts as large as possible.

Constraints

1 <= len(s) <= 500
s consists of lowercase English letters

Learn this in

Patterns & MiscellaneousDSA Study Plan

More from Amazon DSA

Daily Temperaturesmedium Implement Queue using Stackseasy Min Stackmedium Walls and Gatesmedium Flood Filleasy

Concept primerPREVIEW

Background Knowledge

The "Partition Labels" problem falls under the category of Greedy and Interval problems. To tackle this problem, it's essential to understand the basics of greedy algorithms, which involve making the locally optimal choice at each step with the hope that these local choices will lead to a globally optimum solution. In the context of interval problems, we often deal with overlapping or non-overlapping intervals and need to find the most efficient way to partition or cover them.

A key concept in solving interval problems is understanding how to represent and manipulate intervals. This can involve finding the start and end points of each interval, as well as determining how intervals overlap or intersect. In the case of the "Partition Labels" problem, we're dealing with a string s and want to partition it into parts such that each letter appears in at most one part. This requires analyzing the frequency and distribution of characters within the string.

To approach this problem, it's also helpful to have a basic understanding of string manipulation and iteration techniques. This includes knowing how to iterate over characters in a string, track the indices of specific characters, and potentially use data structures like dictionaries or lists to store and retrieve information about character positions.

Algorithm/Approach

The general approach to solving the "Partition Labels" problem involves using a greedy algorithm that iterates over the input string s. The algorithm should keep track of the last seen index of each character and use this information to determine the optimal partition points. By making locally optimal choices at each step, the algorithm aims to minimize the number of partitions while ensuring that each letter appears in at most one part.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results