763. Partition Labels

Link

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.

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 <= 500

• s consists of lowercase English letters.

Solution

將每個字元所在的位置整理成interval

然後進行intervals merge, 看最後每個interval的長度

    public List<Integer> partitionLabels(String s) {
        int[][] intervals = new int[26][2];
        
        for(int[] interval : intervals){
            interval[0] = -1;
            interval[1] = -1;
        }        

        //intervals[s.charAt(0) - 'a'][0] = 0;
        for(int i = 0; i < s.length(); i++){
            if(intervals[s.charAt(i) - 'a'][0] == -1){
                intervals[s.charAt(i) - 'a'][0] = i;
            }
            intervals[s.charAt(i) - 'a'][1] = i;
        }    
        Arrays.sort(intervals, (a,b)-> a[0]-b[0]);
        int start = -1, end = -1;
        List<Integer> ret = new LinkedList<>();
        for(int[] interval : intervals){
            if(interval[0] == -1) continue;
            if(start == -1){
                start = interval[0];
                end = interval[1];
            }
            else if(interval[0] <= end){
                end = Math.max(end, interval[1]);
            }
            else if(interval[0] > end){
                ret.add(end-start+1);
                start = interval[0];
                end = interval[1];
            }
        }
        ret.add(end-start+1);
        return ret;
    }