Partition Labels
Partition Labels is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Line Sweep subpattern.
Problem statement
Given the string s, divide it into one or more contiguous, nonempty parts whose concatenation is exactly s. A character may occur in only one part: all occurrences of the same character must be contained within that part, so no character can appear in two different parts.
Among all valid partitions, choose the one with the greatest possible number of parts. The partition with the most parts is unique. Return an array containing the sizes of its parts from left to right.
Example 1:
Input: s = "abac" Output: [3,1] Explanation: The first part is aba and the second is c. Splitting earlier would place the two a characters in different parts.
Example 2:
Input: s = "qrrqst" Output: [4,1,1] Explanation: The first part must contain qrrq because both q occurrences and both r occurrences belong together. The remaining characters can each form their own part.
Example 3:
Input: s = "mnop" Output: [1,1,1,1] Explanation: Each character appears once, so every character can be isolated in its own part.
Constraints:
- 1 <= len(s) <= 10^5 - s contains only lowercase English letters - Every character occurrence in s belongs to exactly one part - The returned sizes are positive integers whose sum is len(s)
Topics and companies
Topics: Greedy, String, Array.
How to practise Partition Labels on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n), where n is the length of s. time and O(1) auxiliary space, excluding the returned result; the last-occurrence array has size 26. space.
Open Partition Labels in the code editor, or read the Partition Labels editorial for a worked solution with its approach and complexity analysis.
Where Partition Labels sits in the DSA pattern sheet
- Greedy Patterns pattern guide
- Line Sweep subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Partition Labels
Other problems that use the same Line Sweep and Greedy Patterns techniques:
- Car Pooling — Medium, same subpattern
- Employee Free Time — Hard, same subpattern
- Interval List Intersections — Medium, same subpattern
- Assign Cookies — Easy, same pattern
- Candy — Hard, same pattern
- Distant Barcodes — Medium, same pattern