LeetCode 763. Partition Labels
題目描述
思路
顯然，如果整個字符串無重複值，那麼字符串的字符個數就是最多劃分的區間個數。
如果有重複值，假設a字符有重複，那麼所有的a必須劃分到同一個區間內，否則a分佈不同區間的話，就不滿足題目要求了。
同理，其他字符也是類似的邏輯。
我們的整體流程是從左往右遍歷字符，當遍歷到一個字符的時候，我們需要快速知道這個字符在字符串後續位置是哪裡，這樣至少知道這個字符串至少應該從哪裡開始切。
例如：abdtydfsdfdasbsssrr這個字符串，當遍歷到第一個a時候，我們需要馬上知道整個字符串後續是否還有a這個字符，此例子中，在字符串的11位置確實還有一個字符a。
我們設置一個right變量，用於記錄當前刀最少要切到的位置，
當遍歷到第一個a字符以後，可以判斷第一刀至少要切到11位置，right記錄為11，
至於後續是否還需要繼續擴散，要繼續遍歷下一個字符b，如果整個字符串中最右邊的b字符沒有超過11位置，則第一到繼續可以保持到11位置來切，
如果整個字符串中的b的最右位置超過了11，如此例，最右邊的b出現在13位置，那麼第一刀位置就要從11擴散到13位置，right記錄為13
如果遍歷到某個字符串的最右邊位置正好是right，則可以從這個位置切一刀。
以此類推，直到遍歷完整個字符串。
根據以上流程，我們需要對數組進行一次預處理，即，記錄每個字符串出現的最右位置，由於題目限定是小寫字母，所以可以通過如下方式來保存每個字符的最右位置
int[] help = new int[26];
for (int i = 0; i < str.length; i++) {
help[str[i] - 'a'] = i;
}
主流程代碼
int right = 0;
int pre = right;
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < str.length; i++) {
// 是否可以將right位置擴散
right = Math.max(right, help[str[i] - 'a']);
if(i == right) {
// 當前位置已經是能擴散的最右位置了
// 收集答案
ans.add(right - pre + 1);
pre = right + 1;
}
}
return ans;
pre記錄上一刀的位置，便於求每個區間的長度（題目要求）， 當前遍歷到的位置i如果正好是目前區間能擴散的最右位置right，則結算。
