# 763. Partition-Labels

difficulty: Medium

&#x20;section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }&#x20;

A string `S` of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and 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.
```

**Note:**

* `S` will have length in range `[1, 500]`.
* `S` will consist of lowercase English letters (`'a'` to `'z'`) only.

## Method One

```java
class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> ans = new ArrayList<>();

        // Method 1 Greedy 核心是Two pointers, 
        // right 始终指向目前最右侧，left指向目前最左
        // 当 i 遇到 right 的时候，说明区间内的所有的字符的都被记录了。

        // int[] lastPositions = new int[26];
        // for(int i = 0; i < S.length(); i++){
        //     char c = S.charAt(i);
        //     lastPositions[c - 'a'] = i;
        // }
​
        // int right = 0;
        // int left = 0;
        // for(int i = 0; i < S.length(); i++){
        //     char c  = S.charAt(i);
        //     right = Math.max(right, lastPositions[c - 'a']);
        //     if( right == i ){
        //         ans.add( right - left + 1 );
        //         left = i + 1;
        //     }
        // }

        // Method 2 转化为 merge interval

        Map<Character, int[]> intervals = new HashMap<>();
​
        for(int i = 0; i < S.length(); i++){
            intervals.putIfAbsent(S.charAt(i), new int[]{i,i});
            intervals.get(S.charAt(i))[1] = i;
        }
        int curLeft = 0;
        int curRight = intervals.get(S.charAt(0))[1];
        for(int i = 1; i < S.length(); i++){
            char c  = S.charAt(i);
            int[] interval = intervals.get(c);
            if(interval[0] >= curRight){
                ans.add(curRight - curLeft + 1);
                curLeft = interval[0];
                curRight = interval[1];
            }else{
                curRight = Math.max(curRight, interval[1]);
                curLeft = Math.min(curLeft, interval[0]);
            }
        }
        ans.add(curRight - curLeft + 1);
        return ans;
    }
}
​
```
