Back to DSA

Partition Labels

medium
Acceptance: 54%
GreedyStringsTwo Pointers

Split a string into the maximum number of contiguous segments such that every character appears in at most one segment. Return the lengths of those segments in order.

Examples

Example 1:
Input:s = "xyzxabcabc"
Output:[4,6]
Example 2:
Input:s = "abcabc"
Output:[6]

Hints

Related Problems

Remove Duplicates from Sorted ArrayeasyValid PalindromeeasyMerge Sorted ArrayeasyMove ZeroeseasyContainer With Most Watermedium
00:00
import java.util.*;

class Solution {
    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 complexityO(n)
Space complexityO(1)