763. Partition Labels#

1. 題目描述

題目連結

A string S of lowercase 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 letters (‘a’ to ‘z’) only.

2. 題目分析

這題意比較難了解，剛開始讀了好幾遍，都沒看懂。意思就是說，将一個長字元串S，進行分割多個子串，分割時必須保證每個字元隻能出現在一個子串中，并且子串必須是最小子串，就是不能繼續分割了。如"ababcbacadefegde"，就還能分割： “ababcbaca”, “defegde”，是以"ababcbacadefegde"不是最小子串。

開始時，這裡有個讓我疑惑的地方是，像這種"ababcbacadefegdehijhklijxwz"，前面部分分割成"ababcbaca", “defegde”, “hijhklij”，但"xwz"是作為一個整體呢，還是繼續分割成"x",“w”,"z"呢？後面經過測試，是後者。仔細想想按題目的意思，"xwz"是需要繼續分割的，“x”,“w”,"z"才是最小子串。

3. 解決思路

首先周遊整個字元串S，記錄每個字元最後出現的下标到一個maxIndex數組中。

然後，周遊字元串的時候，對于字元串S而言，從S最左邊的第一個字母，然後從數組maxIndex中找到該字母在S中最右邊出現的位置，這裡假設為end，如果從S最左邊到end之間有一個字母最右邊的索引在end右邊，那麼更新end，繼續周遊，直到S最左端到i的字母已經全部周遊了一遍，這個時候0~end就是一個最小的分組，将S切分，對end+1到S最右端繼續以上操作，重複執行該操作直到S切分完畢

4. 代碼實作（java）

public List<Integer> partitionLabels(String S) {
        List<Integer> list = new LinkedList<>();
        if(S == null || S.isEmpty()){
            return list;
        }
        int len = S.length();
        int[] maxIndex = new int[26];
        for(int i = 0; i < len; i++) {
            maxIndex[S.charAt(i) - 'a'] = i;
        }

        int start = 0;
        int end = start;
        int i;
        int partitionLen = 0;
        while(end < len){
            i = start;

            while(i <= end && end < len){
                end = Math.max(end, maxIndex[S.charAt(i) - 'a']);
                i++;
            }
            partitionLen = end - start + 1;
            list.add(partitionLen);
            start = end + 1;
            end = start;
        }
        return list;
    }