763. Partition Labels
Partition Labels (LeetCode 763) 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.
How to solve Partition Labels
Partition Labels is a Line Sweep Algorithm problem, part of Greedy Patterns. Master the line sweep technique for interval and geometric problems. Process events in sorted order for overlap counting, skyline, and meeting room problems.
Work towards the solution in these steps:
- For each character, determine where its final occurrence appears in `s`.
- While scanning from left to right, a part cannot end before the last occurrence of any character already inside it.
- Keep the farthest required ending position for the current part and extend it whenever a newly scanned character requires a later ending.
The reference solution runs in O(n) time and O(1) space.
The Partition Labels solution and editorial walks through the full approach with reference code.
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) time and O(1) 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
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
Partition Labels FAQ
What is the LeetCode number of Partition Labels?
Partition Labels is LeetCode problem 763, rated Medium.
What pattern is used to solve Partition Labels?
Partition Labels is a Line Sweep Algorithm problem. It belongs to the Greedy Patterns pattern, in the Line Sweep subpattern.
What is the time complexity of Partition Labels?
The reference solution runs in O(n) time and O(1) space.