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 <= 500s consists of lowercase English letters.This approach uses a greedy method where we determine the possible endpoints of each partition by finding the last occurrence of each character. As we iterate through the string, we expand the end of the current partition to the maximum last occurrence index of all characters seen so far. The current partition ends once the current index matches this endpoint.
This C solution utilizes an array to store the last occurrence index of each character. As we iterate through the string, we calculate the endpoint of the current partition by checking the maximum last occurrence index of the characters seen so far. Once the end of the partition is reached, we record its size and move to the next partition.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string, because we iterate over the string a constant number of times.
Space Complexity: O(1), as the space used for storing last occurrences is constant, not dependent on input size.
Another approach involves performing two passes over the string. The first pass is used to collect the rightmost occurrence of each character, and in the second pass, we calculate the sizes of partitions while maintaining the maximum index of characters on the go.
This C implementation performs a two-step traversal of the given string. Firstly, we map each character's last occurrence to create the partition scopes. In the walk-through, the size of a partition is determined when the maximum index matches the loop index, marking partition boundaries.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) for length n of the string, taking linear scans for mapping and partitioning.
Space Complexity: O(1) since the space needed does not grow in relation to input size.
| Approach | Complexity |
|---|---|
| Greedy Method with Last Occurrence | Time Complexity: O(n), where n is the length of the string, because we iterate over the string a constant number of times. |
| Two-Pass Trick | Time Complexity: O(n) for length n of the string, taking linear scans for mapping and partitioning. |
Partition Labels • Kevin Naughton Jr. • 59,564 views views
Watch 9 more video solutions →Practice Partition Labels with our built-in code editor and test cases.
Practice on FleetCode