763. Partition Labels - Medium

前往題目

想法

• 每個字母的第一個和最後一個為區間

思路

1. 記錄每個字母的最後一位的位置
2. 開始循環s，每次更新當前的最後一位在哪，取最遠的（因為最大區間不能被切開，否則會有同個字母分隔兩邊的情況）
3. 遇到盡頭時（當前字母最後一位與最遠的同位），切開並記錄

這題是把每個字母都當區間來看，只是開頭並不重要，重要的是每個字母最後在哪裡出現，因為不能在中途就切開，不然就會出現同個字母被切開的情況，這也是題目不允許的

Code

class Solution {
    public List<Integer> partitionLabels(String s) {
        Map<Character, Integer> map = new HashMap();

        // Build up the last occurence of each character map
        for (int i = 0; i < s.length(); ++i) {
            map.put(s.charAt(i), i);
        }

        int prev = -1;
        int max = 0;
        List<Integer> res = new ArrayList();

        // Start partitioning
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            
            // Update the last occurence
            max = Math.max(max, map.get(c));
            
            // Reach the last occurence of the current interval
            if (max == i) {
                res.add(max - prev);
                prev = i; // Set to the last split
            }
        }
        return res;
    }
}