Partition Labels

Partition string into as many parts as possible so each letter appears in at most one part.

Example 1

Input: s="ababcbacadefegdehijhklij" → Output: [9,7,8]

Example 2

Input: s="eccbbbbdec" → Output: [10]

Solution Approach

Record last occurrence of each character. Expand current partition when current index equals its end.

Record last index of each character
Track start=0 and end=0 of current partition
For each char: end = max(end, last[char])
When i == end: partition length = end-start+1, start=end+1

Java

public List<Integer> partitionLabels(String s) {
    int[] last = new int[26];
    for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
    List<Integer> result = new ArrayList<>();
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        end = Math.max(end, last[s.charAt(i) - 'a']);
        if (i == end) {
            result.add(end - start + 1);
            start = end + 1;
        }
    }
    return result;
}

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