Skip to content
AI360Xpert
Back to Greedy
Medium

Partition Labels

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.

Examples

Input:s = "ababcbacadefegdehijhklij"
Output:[9,7,8]
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.
Input:s = "eccbbbbdec"
Output:[10]
We cannot partition it into more parts because 'e' and 'c' appear at the beginning and the end.

Constraints

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

Greedy with Last Occurrence

Approach

First, we iterate through the string to record the last index of occurrence for each character in a hash map or array. Then, we iterate through the string again, maintaining the start of the current partition (`start`) and the furthest index any character in the current partition reaches (`end`). As we process each character `c` at index `i`, we update `end = max(end, last_occurrence[c])`. If we reach `i == end`, it means all characters we have seen so far do not appear after this index. This is the end of a valid partition. We add `end - start + 1` to our result, and start a new partition by setting `start = i + 1`.

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(1)

Time complexity is O(n) as we traverse the string twice. Space complexity is O(1) because the hash map or array for the last occurrences stores at most 26 lowercase English letters.

Solution.java
class Solution {    public List<Integer> partitionLabels(String s) {        int[] last = new int[26];        // Record the last occurrence of each character        for (int i = 0; i < s.length(); i++) {            last[s.charAt(i) - 'a'] = i;        }                List<Integer> res = new ArrayList<>();        int start = 0;        int end = 0;                for (int i = 0; i < s.length(); i++) {            end = Math.max(end, last[s.charAt(i) - 'a']);                        if (i == end) {                res.add(end - start + 1);                start = i + 1;            }        }                return res;    }}