763. Partition Labels - Medium

前往題目

想法

• 不知道如何判斷partition在何時結束

思路

其實很簡單，疊代s的字符，每次都取最大的終點，這樣在一個partition結束時指針就會剛好等於end，因為此區間沒有更遠的字符了

1. 紀錄每個字符(總共26個小寫字母)的終點
2. 疊代s的所有字符，每次更新size和終點
3. 指針等於終點的時候就是一個partition結束的時候
4. 加入結果，並且歸零size

Code

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();
        int[] map = new int[26]; // alphabet -> lastIndex
        
        // Store each character's last position
        for (int i = 0; i < s.length(); ++i) {
            map[s.charAt(i) - 'a'] = i;
        }

        // Keep track of the partition size
        int size = 0;
        // The temp end of the partition
        int end = 0;

        // Go through the string
        for (int i = 0; i < s.length(); ++i) {
            ++size;

            end = Math.max(end, map[s.charAt(i) - 'a']);    
            
            // Reach the end of the current partition
            if (i == end) {
                res.add(size);
                size = 0;
            }
        }
        return res;
    }
}