Partition string into as many parts as possible so each letter appears in at most one part.
Input: s="ababcbacadefegdehijhklij" → Output: [9,7,8]
Input: s="eccbbbbdec" → Output: [10]
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
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)