LeetCode 763. Partition Labels

作者：Grey

原文位址：LeetCode 763. Partition Labels

題目連結

顯然，如果整個字元串無重複值，那麼字元串的字元個數就是最多劃分的區間個數。

如果有重複值，假設a字元有重複，那麼所有的a必須劃分到同一個區間内，否則a分布不同區間的話，就不滿足題目要求了。

同理，其他字元也是類似的邏輯。

我們的整體流程是從左往右周遊字元，當周遊到一個字元的時候，我們需要快速知道這個字元在字元串後續位置是哪裡，這樣至少知道這個字元串至少應該從哪裡開始切。

例如：<code>abdtydfsdfdasbsssrr</code>這個字元串，當周遊到第一個<code>a</code>時候，我們需要馬上知道整個字元串後續是否還有<code>a</code>這個字元，此例子中，在字元串的11位置确實還有一個字元<code>a</code>。

我們設定一個right變量，用于記錄目前刀最少要切到的位置，

當周遊到第一個a字元以後，可以判斷第一刀至少要切到11位置，right記錄為11，

至于後續是否還需要繼續擴散，要繼續周遊下一個字元b，如果整個字元串中最右邊的b字元沒有超過11位置，則第一刀可以繼續保持到11位置來切，

如果整個字元串中的b的最右位置超過了11，如此例，最右邊的b出現在13位置，那麼第一刀位置就要從11擴散到13位置，right記錄為13

如果周遊到某個字元串的最右邊位置正好是right，則可以從這個位置切一刀。

以此類推，直到周遊完整個字元串。

根據以上流程，我們需要對數組進行一次預處理，即，記錄每個字元串出現的最右位置，由于題目限定是小寫字母，是以可以通過如下方式來儲存每個字元的最右位置

主流程代碼

pre記錄上一刀的位置，便于求每個區間的長度（題目要求）， 目前周遊到的位置i如果正好是目前區間能擴散的最右位置right，則結算。

算法和資料結構筆記