763. Partition Labels

Interval

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    private static class Interval implements Comparable<Interval> {
        private final int startIndex;
        private int endIndex;

        public Interval(int startIndex, int endIndex) {
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        @Override
        public int compareTo(Interval o) {
            return Integer.compare(startIndex, o.startIndex);
        }
    }

    public List<Integer> partitionLabels(String s) {
        Map<Character, Interval> intervalMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            Interval interval = intervalMap.get(c);
            if (interval == null) {
                interval = new Interval(i, i);
                intervalMap.put(c, interval);
            } else {
                interval.endIndex = i;
            }
        }

        List<Interval> intervalList = new ArrayList<>(intervalMap.values());
        Collections.sort(intervalList);

        List<Interval> combinedIntervalList = new ArrayList<>();
        combinedIntervalList.add(intervalList.get(0));

        for (int i = 1; i < intervalList.size(); i++) {
            Interval lastInterval = combinedIntervalList.get(combinedIntervalList.size() - 1);
            Interval currInterval = intervalList.get(i);
            if (lastInterval.endIndex >= currInterval.startIndex) {
                lastInterval.endIndex = Math.max(lastInterval.endIndex, currInterval.endIndex);
            } else {
                combinedIntervalList.add(currInterval);
            }
        }

        List<Integer> lengthList = new ArrayList<>(combinedIntervalList.size());
        for (Interval interval : combinedIntervalList) {
            lengthList.add(interval.endIndex - interval.startIndex + 1);
        }

        return lengthList;
    }
}

Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> resultList = new ArrayList<>();

        int[] lastIndexMap = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastIndexMap[s.charAt(i) - 'a'] = i;
        }

        int startIndex = 0;
        while (startIndex < s.length()) {
            int endIndex = startIndex;
            for (int i = startIndex; i <= endIndex; i++) {
                endIndex = Math.max(endIndex, lastIndexMap[s.charAt(i) - 'a']);
            }

            resultList.add(endIndex - startIndex + 1);
            startIndex = endIndex + 1;
        }

        return resultList;
    }
}

References

763. Partition Labels